문제
해결
제목에서 스포를 당했고, 이 문제는 그리디 기법으로 푸는 문제이다.
나는 사람들을 몸무게 순서대로 오름차순 정렬 후 양 끝에 있는 사람들의 몸무게 합이 limit 이하면 둘을 한번에 보트에 실어 나르고, 초과라면 몸무게가 많은 사람만 구명보트에 담아 날랐다.
이를 증명하기 위해 "현재 사람들 중에서 가장 몸무게가 큰 사람과 가장 작은 사람의 합이 limit 이하이면 둘을 보트에 실어 나르고, 아니라면 큰 사람 혼자만 보트에 담아 나르는게 보트를 최소로 사용하는 방법이다." 라는 명제를 세웠다.
이를 귀류법으로 증명한다. 가장 가벼운 사람을 s, 가장 무거운 사람을 h라 하자.
s+h > limit인 경우: h는 가장 가벼운 s와도 못 타므로 누구와도 함께 탈 수 없다. 따라서 어떤 최적해에서든 h는 혼자 탄다.
s+h ≤ limit인 경우: 귀류법으로 증명한다.
부정 가정: s와 h를 같은 보트에 태우는 최적해가 하나도 없다.
임의의 최적해 O를 잡는다. 가정에 의해 O에서 s와 h는 다른 보트에 있다.
- h가 혼자 탄 경우: s를 h의 보트로 옮긴다. s+h ≤ limit이라 유효하고, 보트 수는 늘지 않는다.
- h가 y와 탄 경우: s의 짝을 x(없을 수도 있다)라 하면, (h,y),(s,x)를 (h,s),(y,x)로 바꾼다. x ≤ h이므로 x+y ≤ h+y ≤ limit이라 유효하고, 보트 수는 같다.
어느 경우든 보트 수가 O 이하이면서 s와 h가 함께 탄 해가 만들어진다. 이 해도 최적해이므로 가정과 모순이다. 따라서 s와 h를 함께 태우는 최적해가 존재한다.
s와 h를 함께 태운 최적해에서 그 보트를 빼면, 나머지는 남은 사람들에 대한 최적해여야 한다. 왜냐하면 남은 사람들을 더 적은 보트로 태울 수 있다면 전체 보트 수도 줄어들어 최적해라는 것에 모순이기 때문이다.
그 뒤 남은 사람들은 같은 형태의 더 작은 문제이므로, 귀납적으로 전체 그리디가 최적이다.
코드
int solution(vector<int> p, int l) {
int answer = 0;
sort(p.begin(), p.end());
int st = 0;
int en = p.size() - 1;
while(st < en)
{
if(p[st] + p[en] <= l) st++;
answer++;
en--;
}
if(st == en) answer++;
return answer;
}