백준 11092(Safe Passage)

https://www.acmicpc.net/problem/11092

11092번: Safe Passage

 

 

투명망토를 쓰고 학교로 돌아가는데 한번에 최대 두명만 쓸 수 있고, 속도는 더 느린쪽에 맞춰서 이동한다. 

그리고 모두 학교로 다시 돌아와야 되기 때문에 입구까지 투명망토를 전달할 한 명도 필요하다. 모두 학교로 다시 돌아갈 때까지의 최단 시간은?

 

음 직관적인 문제라고 해야되나 간단한 비교를 통해서 찾을 수 있는 것이지만 찾기가 어려웠다. 

 

먼저 생각할 수 있는건 느린놈들끼리 보내는게 시간을 줄이는데에 도움이 된다. 

 

어차피 둘 중에 더 느린 사람의 속도에 맞추기 때문에 단순하게 이렇게 생각할 수 있다. 

 

그렇다면 이제 학교로 가는 경우만 말고, 입구로 돌아가는 경우까지 생각해보자

 

입구로 돌아갈때 가장 시간이 적게 걸리려면 학교에 있는 사람 중에서 가장 빠른 사람을 혼자 보내는 경우이다. 

 

이 경우는 조금만 생각해봐도 무조건 가장 빠른 사람 보내는게 최종적으로 시간이 적게 걸린다는 걸 알 수가 있다. 

 

 

 

문제는 학교에 있는 사람 중에서 가장 빠른 사람이 누가 되느냐이다. 

 

학교에 있는 사람이 무조건 전체에서 가장 빠른 사람이면 좋겠지만 그렇지 않은 경우에 가장 최단시간인 경우가 있을 수 있기 때문이다. 

 

예시를 들면 

 

4

 

1 2 7 10

 

인 경우에 

 

1 2 를 학교로 보내고

1을 입구로 보내고 

7 10 을 학교로 보내고 

2를 입구로 보내고

1 2를 학교로 보내고 

 

이 경우가 최단 시간이 되는 경우인데, 4번째 줄에서 보이듯이 1이 아닌 2가 학교에 있는데도 최단시간이 만들어 졌다. 

 

만약에 1을 계속해서 학교로 보냈다가 입구로 보냈다가를 반복하면 

 

1 2를 학교로 보내고

1을 입구로 보내고

1 10을 학교로 보내고

1을 입구로 보내고

1 7을 학교로 보내고 

 

21의 시간이 걸리게 되고, 최단 시간이 아니게 된다. 

 

또 가장 느린 사람과 그 다음 느린 사람을 같이 보낸 경우가 아닌 경우

 

1 3 6 8 12

 

에서 보자 

 

1 3 학교로 보내고 

1 입구로 보내고 

6 8 학교로 보내고 

3 입구로 보내고 

1 12 학교로 보내고 

1 입구로 보내고 

1 3 학교로 보내고 

 

만약에 느린사람끼리 묶어두지 않으면 

 

위와 같이 12 + 6 인 경우가 아닌 12+8인 경우가 발생하게 된다. 따라서 최고로 느린 사람과 그 다음 느린사람을 최대한 묶어서 학교로 보내야 한다. 

 

위에 경우를 정리하면 

 

전제조건은 가장 느린사람들끼리 최대한 묶어서 보낸다. 

 

입구로 보낼애가 누군지 시간비교를 통해서 결정한다. 

(반드시 가장 작은 두 명 중 한명이 된다.)

 

 

증명은 없다 그냥 그런것같다. 

 

그래서 나는 먼저 가장 빠른 둘을 학교로 보냈다. (맨 마지막에 보내더라도 위 전제조건 1에 위배되지 않는다. 그리고 입구로 보내야 하므로, 가장 빠른애가 학교에 있어야 한다.)

 

그 뒤에 학교에 있는 애 중에서 가장 빠른애를 입구로 보냈다.

 

이제 비교를 한다. 

 

두 번째로 빠른 애를 입구로 이동시키는데에 이용할 것인지 가장 빠른애를 이용할 것인지

 

만약에 4 100 101 102 103 이 있다고 하면 

 

100 이 학교에 있고, 

 

4 101 102 103이 입구에 있다. 

 

학교로 가장 큰 두놈을 묶어서 보내보자 

 

103 102 학교로 보낸다

100 입구로 보낸다 (학교에서 있는 것 중에서 가장 빠른 애)

4 100 학교로 보낸다. 

4 입구로 보낸다.

 

vs

 

4 103 학교로 보낸다. (4가 가장 빠르므로 4를 학교로 보내야 입구로 보낼 때 4를 쓸 수 있다)

4 입구로 보낸다.

4 102 학교로 보낸다. 

4 입구로 보낸다. 

 

두 경우 모두 위의 상황에서 102와 103만 보낸 경우이다. 

따라서 전 후 상황이 같으므로 이런식으로 비교해서 더 빠른 걸 선택해도 상관이 없다. 

 

위 경우에는 밑의 경우가 더 빠르므로 밑에껄 선택해서 사용한다. 

 

하나의 경우를 더 확인해보자

4 100 1234 12345 123456 

 

이 있는 경우를 확인해보자 

 

4 100 학교

4 입구

에서 

 

123456 12345 학교 

100 입구

4 100 학교 

4 입구

12345 4 학교 

 

vs

 

123456 4 학교

4 입구

12345 4 학교 

4 입구 

1234 4 학교

 

위에 경우가 더 최적의 상황이다. 

 

따라서 매번 비교를 통해서 가장 빠른 애를 이용할 것인지 그 다음 빠른것을 이용할 것인지 값 비교를 통해서 확인한다. 

 

위의 상황을 모두 학교로 갈때까지 반복한다.

 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 5001

int N, num, sum, start1, start2;
int speed[16];
bool dorm[MAX];
bool done;

int main() {
	cin >> N;
	num = N;
	for (int i = 0; i < N; i++) {
		cin >> speed[i];
	}
	sort(speed, speed + N);
	start1 = speed[0];
	start2 = speed[1];
	dorm[start2] = true;
	num -= 2;
	sum += start2;
	while (num) {
		sum += start1;
		num += 1;
		int n1 = -1, n2 = -1;
		for (int i = 0; i < N; i++) {
			if (dorm[speed[i]]) continue;
			if (n1 < speed[i]) {
				n2 = n1;
				n1 = speed[i];
			}
		}
		if (num == 2) {
			sum += n1;
			num -= 2;
		}
		else {
			int left = n1 + n2 + start1;
			int right = n1 + start2 * 2;
			if (left < right) {
				sum += left;
			}
			else {
				sum += right;
			}
			dorm[n1] = true;
			dorm[n2] = true;
			num -= 3;
		}
	}
	cout << sum << "\n";
}