[ SWEA ] 2383. 점심 식사시간

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

SW Expert Academy

 

풀이 방법

n명의 사람이 2개의 계단 중 하나를 선택하여 내려갈 수 있다. 계단을 선택하는 전체 경우의 수는 2^n인데, n이 최대 10이기 때문에 모든 경우에 대하여  소요 시간을 구하였다.

 

각 사람들이 계단을 선택하는 조합을 구하고, 구한 조합에 대하여 calc_time() 함수를 통해 소요 시간을 구한다. 그리고 그 중 최소 소요시간을 result에 업데이트해나간다.

void min_time(int n) {
	if (n == num_people) {
		int ret = calc_time();
		result = min(result, ret);
		return;
	}
	choose_stair[n] = false;	// choose stair 0
	min_time(n + 1);
	choose_stair[n] = true;		// choose stair 1
	min_time(n + 1);
}

 

calc_time()

각 사람들이 선택한 계단까지 도착하는 시간을 구한다. 그 후, 빨리 도착한 순서대로 계단을 내려갈 수 있기 때문에 오름차순으로 정렬한다.

// calculate time to move
for (int i = 0; i < num_people; i++) {
	if (choose_stair[i]) {
		dist_to_stair1.push_back(dist[1][i]);
	}
	else {
		dist_to_stair0.push_back(dist[0][i]);
	}
}
sort(dist_to_stair0.begin(), dist_to_stair0.end());
sort(dist_to_stair1.begin(), dist_to_stair1.end());

 

각 계단에 대해 모든 사람이 내려가는 소요 시간을 구한다. 최대 3명까지 계단을 내려갈 수 있기 때문에 window 크기를 3으로 하여 sliding window로 구현했다. 다음과 같이 경우를 나누었다.

• case 1: 계단을 이용 중인 사람이 3명보다 적을 때 → 다음 사람은 제약 없이 내려간다.
• case 2: 계단을 이용 중인 사람이 3명일 때 → 가장 먼저 내려간 사람의 도착 시간을 구하여 내보낸다.
  • case 2-1: 대기 중인 사람이 있을 때 → 대기 시간까지 계산하여 내려 보낸다.
  • case 2-2: 대기 중인 사람이 없을 때 → do nothing
• case 3: 더 이상 내려갈 사람이 없을 때 → 가장 먼저 내려간 사람의 도착시간을 구해 내보낸다.

int start = 0, end = 0, n = dist_to_stair0.size();

while (start < n) {
	if (end >= n) { // case 3
		dist_to_stair0[start] = dist_to_stair0[start] + 1 + map[stairs[0].first][stairs[0].second];
		start++;
	}
	else if (end - start >= 3) { // case 2
		dist_to_stair0[start] = dist_to_stair0[start] + 1 + map[stairs[0].first][stairs[0].second];
		if (dist_to_stair0[end] < dist_to_stair0[start]) { // case 2-1
			dist_to_stair0[end] = dist_to_stair0[start] - 1;
			start++;
			end++;
		}
		else { // case 2-2
			start++;
		}
	}
	else { // case 1
		end++;
	}
}

 

각 계단에 대하여 소요 시간을 구하고, 이 중 더 큰 값이 전체 소요 시간이다.

return max(max(dist_to_stair0), max(dist_to_stair1));

 

전체 코드는 여기서 확인할 수 있다.