[구현훈련] 벽돌쌓기

문제

벽돌쌓기를 하자. 인부들이 N명 있고 벽돌 쌓기를 할 작업 갯수가 T만큼 있다. 한명의 인부가 A번 만큼 작업을 하게 되면 R만큼 쉬는시간을 부여한다. 또한 작업 개수 T만큼의 작업 시간이 주어진다.

위의 규칙으로 작업을 할 때 작업이 끝날때까지의 시간을 구하라.

 

예를 들어 3명의 인부(N=3), 10개의 작업(T=10), 휴식까지 3번의 작업(A=3), 쉬는 시간 2(R=2)라고 주어지고

각 작업시간이 1 2 1 4 3 2 1 5 2 3 라고하면 작업시간표는 아래와 같다. 작업시간은 10

 

N이 2, T가 8, A가 3, R이 2이고 작업시간이 각각 2 3 4 1 1 5 4 2 일 경우는 아래와 같다. 작업 시간은 13

---

입력

case1

3 10 3 2
1 2 1 4 3 2 1 5 2 3

 

case2

2 8 3 2
2 3 4 1 1 5 4 2

 

출력

case1

10

 

case2

13

 

 

---

문제해결

단순하게 요구사항을 구현하는 문제이나 다소 규칙이 한눈에 이해되지 않아서 바로 이해하기는 어려웠다. 다만 손으로 먼저 천천히 따라가면서 필요한 내용을 메모하고 디버깅하다보는 것이 큰 도움이 됐다. 내가 생각한 아이디어는 작업자를 정할떄 최소 작업시간을 구하여 최소작업 시간과 인부의 작업시간을 비교하는 것이다.

1) 인부의 수만큼 배열을 만들어, 작업시간을 가중치로 더하자

2) A번 만큼 cnt를 세어야하므로 cnt 배열을 만들자

3) idx를 위한 작업배열 인덱스 tp, 인부배열 인덱스 cp를 활용하자

4-a) 작업시간 배열를 돌며 현재의 가중치가 min값보다 작거나 같으면 해당 인부에게 작업을 할당한다.

   할당 시에 작업cnt가 3이면 작업할당 대신 쉬는시간을 부여하고 cnt를 초기화한다.

   작업cnt가 3보다 작으면 작업할당하여 가중치를 늘리고 tp 및 cnt를 증가시킨다.

4-b) 현재 가중치가 min값보다 크면 다음 작업자로 이동한다.

5) cp가 마지막 작업자까지 갔을때 min값을 갱신한다.

 

단번에 아이디어를 도출하기는 어렵겠지만 손으로 풀면서 반복하다보면서 어느정도 정리가 됐다.

#include <stdio.h>


int N; //작업자 수
int T; //작업 수
int A; //연속 작업 값
int R; //쉬는 시간 값
int task[100+10];
//작업자 배열을 만들자. 작업자배열의 값은 작업시간의 누적 가중치로 하자
int worker[10+1];
//작업자별 작업 cnt를 만들자.
int worker_cnt[10+1];
int minT=0;
int ans;

void Input(){
	scanf("%d %d %d %d", &N, &T, &A,&R);
	for(int i=0; i<T; i++)
	{
		scanf("%d", &task[i]);
	}
}

void FindminT()
{
	minT=worker[0];
	for(int i=1; i<N; i++)
	{
		if(worker[i]<minT)
			minT=worker[i];
	}
}

void Solve()
{
	int tp = 0; //작업 pointer
	int cp = 0; //worker pointer
	
	while(tp < T) //작업 총 개수를 다 돌때까지.
	{
		//현재의 누적치가 minT보다 같거나 작으면 go
		if(worker[cp] <= minT)
		{
			if(worker_cnt[cp]==A) //현재 작업자의 cnt가 A와 같다면
			{
				worker[cp]+=R;  //쉬는시간부여
				worker_cnt[cp]=0; //cnt 초기화
			}
			else
			{
				worker[cp]+=task[tp++]; //작업시간 누적 및 tp 증가
				worker_cnt[cp]++; //cnt 누적
			}
		}
        
		if(cp == N-1) FindminT(); // 마지막작업자까지 닿으면 최소 minT 갱신
		cp = (cp+1)%N;	// 다음 작업자로 이동
	}
	
	
}

int main() {
	Input();
	Solve();

	int ans = -1;
	for(int i=0; i<N; i++)
	{
		if(worker[i]>ans) ans = worker[i];
	}
	
	printf("%d", ans);
	
	return 0;
}