[ SWEA / 4408 ] 자기 방으로 돌아가기 (C++)

SW Expert Academy

 

난이도 : D4 
알고리즘 유형 : 완전탐색 
풀이 시간 : 24분 

문제 풀이 

숙소에는 다음과 같이 긴 복도가 있고, 방이 서로 마주보게 배치되어 있다. 모든 학생들은 현재 위치에서 자신의 방으로 돌아가려고 하는데, 만약 두 학생이 자기방으로 돌아가면서 지나는 복도의 구간이 겹치면 두 학생은 동시에 돌아갈 수 없다.

이동하는데는 거리에 관계없이 1 단위시간이 걸린다.

숙소

 

이 문제에서 가장 중요하게 생각해야 할 부분은 방은 서로 마주보고 있는 것이다.

 

이동하는 데 거리와 상관없이 1 단위시간이 걸린다고 하였기 때문에, 문자는 간단히 완전탐색으로 풀어낼 수 있다.

 

우선, 복도 배열을 생성해주고, 이동하는데 걸린 시간을 저장해 줄 것이다. 한 방에서 다른 방으로 이동하는 경로를 찾은 다음, 단위시간을 1씩 증가시켜 줄 것이다.

여기서 방이 서로 마주보고 있다는 점에 주목해야 한다. 방은 총 400개가 존재하지만, 마주보고 있는 방은 한 복도를 공유하기 때문에, 두 방의 복도를 하나로 생각해야된다.

 

이후 입력을 살펴본다. 만약 방 번호가 홀수인 경우, 2로 나눈 값 + 1을 진행해주어 현재 공유하는 복도의 번호를 찾을 수 있다. 이렇게 출발지와 도착지의 복도를 찾은 뒤, 순회하며 1 단위시간만큼 더해주면 된다.

 

마지막으로, 복도의 최대값을 찾으면 그 값이 모든 학생들이 이동하는 데 걸린 시간이 된다.

 

최악의 경우, 시간복잡도는 $O(N * 200)$이 소요된다.

 

코드

/*
조교들의 눈을 피해 자기방으로 돌아가려고 한다. 
모든 학생들은 현재 위치에서 자신의 방으로 돌아가려고 한다.
복도는 한 학생만 사용된다.

최소 몇 단위시간만에 모든 학생이 이동할 수 있는지 구하기

풀이 : 
방 번호 <= 400 
-> 복도는 하나니까 200으로 설정
방에 들어가기 위해 단위시간이 걸리니까 누적합 사용해서 다 더한 뒤 최댓값 출력하기
-> 최악의 경우, 200 * 200
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int t, n;
int floors[201] = { 0, };

int main() {
	cin >> t;
	for (int tc = 1; tc < t + 1; tc++) {
		memset(floors, 0, sizeof(floors));
		cin >> n;
		vector<pair<int, int>> arr(n);
		for (int i = 0; i < n; i++)
			cin >> arr[i].first >> arr[i].second;
		
		// 순회 시작
		for (int i = 0; i < n; i++) {
			int start, end;

			if (arr[i].first < arr[i].second) {
				// 복도 세팅
				if (arr[i].first % 2)
					start = arr[i].first / 2 + 1;
				else
					start = arr[i].first / 2;
				if (arr[i].second % 2)
					end = arr[i].second / 2 + 1;
				else
					end = arr[i].second / 2;
			}
			else {
				if (arr[i].first % 2)
					end = arr[i].first / 2 + 1;
				else
					end = arr[i].first / 2;
				if (arr[i].second % 2)
					start = arr[i].second / 2 + 1;
				else
					start = arr[i].second / 2;
			}
			for (int i = start; i <= end; i++)
				floors[i]++;
		}

		int ans = 0;
		for (int i = 0; i < 401; i++)
			ans = max(ans, floors[i]);

		cout << '#' << tc << ' ' << ans << '\n';
	}
	return 0;
}

배운 점 

싸피에서 알고리즘 수업을 들을 당시 풀었던 문제였다.

당시에는 매우 고전하여 2시간이 넘도록 문제를 풀지 못하였다. 하지만, 이번에는 금방 알고리즘을 떠올리고 풀어나간 것을 보니 확실히 알고리즘을 풀어나갈수록 성장하고 있다는 모습이 보여서 뿌듯하다 !