본문 바로가기

알고리즘/SWEA

2477. 차량 정비소

static int N, M, K, A, B;
static int reception[10]; //original value
static int repair[10]; //original
static int reception_timer[2][10]; //고객번호, 타이머
static int repair_timer[2][10]; //고객번호, 타이머

static bool is_finish()
{
	for (int i = 1; i <= N; i++)
	{
		//접수 창구를 사용하고 있는 고객이 있다면
		if (reception_timer[0][i])
			return false;
	}
	//접수 창구를 이용하고 있는 고객이 없음,
	return true;
}

static int solution()
{
	queue<pair<int, int>> reception_q; //고객번호, 도착시간
	queue<pair<int, int>> repair_q; //고객번호, 사용한 접수 창구
	int last, ret = 0;

	scanf("%d %d %d %d %d", &N, &M, &K, &A, &B);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &reception[i]);
		reception_timer[0][i] = 0;
	}
	for (int i = 1; i <= M; i++)
	{
		scanf("%d", &repair[i]);
		repair_timer[0][i] = 0;
	}
	for (int i = 1; i <= K; i++)
	{
		scanf("%d", &last);
		reception_q.push({ i, last });
	}

	int start_time = reception_q.front().second;
	bool is_end = false;
	//시뮬레이션에서는 한 순간에 하나의 작업만 할 수 있다.
	for (int t = start_time; !is_end; t++)
	{
		for (int i = 1; i <= N; i++) //먼저 모든 접수 창구에 대해 스케줄링 하면서
		{
			if (reception_timer[0][i]) //고객이 할당 되었다면,
			{
				reception_timer[1][i] -= 1; //타이머 동작
				if (reception_timer[1][i] == 0) //타이머 만료
				{
					repair_q.push({ reception_timer[0][i], i }); //정비 큐로
					reception_timer[0][i] = 0; //할당 가능하도록 설정,
					i -= 1; //스케줄링 대상으로 다시 설정, 핵심
				}
			}
			else //고객을 할당 할 수 있다면,
			{
				if (reception_q.empty())
					continue;

				int arrived_time = reception_q.front().second;
				if (arrived_time <= t) //해당 고객이 현재시간 이전에 도착했다면
				{
					reception_timer[0][i] = reception_q.front().first; //고객번호 할당
					reception_timer[1][i] = reception[i]; //타이머 설정
					reception_q.pop(); //해당 고객을 할당했으니 큐에서 제거,
				}
			}			
		}

		for (int i = 1; i <= M; i++) //모든 정비 창구에 대해 스케줄링 하면서
		{
			if (repair_timer[0][i]) //고객이 할당 되었으면
			{
				repair_timer[1][i] -= 1; //타이머 동작
				if (repair_timer[1][i] == 0) //타이머 만료
				{
					repair_timer[0][i] = 0; //할당 가능 하도록 설정
					i -= 1; //스케줄링 대상으로 다시 설정
				}
			}
			else //할당 할 수 있다면
			{
				if (repair_q.empty())
					continue;

				repair_timer[0][i] = repair_q.front().first; //고객번호 등록
				repair_timer[1][i] = repair[i]; //타이머 설정
				if (i == B && repair_q.front().second == A) //A접수창구와 B정비창구 이용 시
					ret += repair_q.front().first; //고객번호를 더함
				repair_q.pop(); //큐에서 제거
				if (is_finish() && repair_q.empty())
				{
					//마지막 고객까지 정비 창구를 이용하는 것이 탈출의 조건이라면 이는 잘못된 생각...
					//그 이전 고객이 제일 긴 딜레이를 가진 접수 창구를 이용한다면
					//마지막 고객이 정비 창구를 이용하더라도, 그 이전 고객이 접수 창구에 있기 때문.
					is_end = true;
					break;
				}
			}
		}
	}

	if (!ret)
		ret = -1;
	return ret;
}

시뮬레이션 문제에서 항상 초점을 맞춰야 할 부분은 시간의 흐름에서 상황 단위로 처리해야 한다는 것과,

작업이 어떻게 이루어 지는 가이다.

 

이 문제에서 시간이 흐르는 것이 배경이고,

시간이 흐르는 과정에서 초점을 맞춰야 할 상황은 접수창구와 정비창구의 상황이다.

두 창구 모두 고객을 할당할 수 있는지, 혹은 할당되었는지를 주의 깊에 봐야한다.

 

그리고 시간이라는 특성 상 한순간에 하나의 작업만 이루어 질 수 있다.

즉, 하나의 상황을 처리하면 다른 상황을 처리 할 수 없다는 것이다.

 

예로, 접수 창구에 고객을 할당 할 수 있으면 할당하는 것만 해야한다.

반대로 고객이 할당된 접수창구에서는 타이머를 작동 시켜야 한다.

 

처음에는 고객을 할당한 순간 같이 타이머가 동작되는 식으로 코드를 작성하였다. 어떻게 보면 논리적으로 맞지 않는 상황이다.

 

다음으로 까다로웠던 부분은 타이머가 만료된 순간이다.

타이머가 만료된 순간을 또 다른 상황으로 봐야 할 지에 대한 것이다.

이럴때는 예제를 잘 보면 된다.

 

접수 창구의 타이머가 2인 곳에 t=0인 순간 부터 고객이 할당되었고, t=2인 순간 정비 창구로 이동하였다.

즉, 타이머가 만료되는 순간 해당 고객을 정비 창구 큐로 보내는 것이 맞다는 것이다.

그리고 이 순간에는 해당 접수 창구는 다른 고객이 할당될 수 있기 때문에 이를 위해 인덱스를 다시 조정해야 한다.

이 역시 예제를 보면 알 수 있다.

 

마지막은 시뮬레이션의 종료 순간이다.

예전에 작성했던 코드와 다시 작성한 코드에서 공통적으로 했던 실수는 가장 늦게온 고객이 정비 창구에 할당 되는 순간이었다.

그러나 주석에 언급한 것 처럼 접수 시간이 엄청 긴 곳에 첫번째 고객이 할당되고, 접수 시간이 엄청 짧은 곳에 마지막 손님이 접수되면 마지막 손님이 정비 창구에 할당 된 순간 첫번째 고객은 아직 접수 창구에 있을 수 있다.

그렇기 때문에 접수 창구를 순회하면서 모든 접수 창구가 비었는지 확인하고, 정비 창구 큐도 비었는지 확인해야 하는 것이다.

 

 

//주의사항 및 정리

1. 시뮬레이션 종료 조건에 대한 정확한 순간에 대한 이해

2. 시뮬레이션에서는 상황에 초점을 맞추고 한 순간에 하나의 상황만 처리 가능하므로 if~else 로 처리해야 하며, 점검하고 있는 대상이 다시 스케줄링에 대상이 될 수도 있다는 점.

3. 내가 의도한 배열을 사용하고 있는지 주의 할 것. 변수에 그 용도를 정확히 적어 놓을 것.

 

'알고리즘 > SWEA' 카테고리의 다른 글

1949. 등산로 조성  (0) 2021.11.09
2115. 벌꿀 채취  (0) 2021.11.09
2117. 홈 방범 서비스  (0) 2021.11.09
1952. 수영장  (0) 2021.11.09
4014. 활주로 건설  (0) 2021.11.09