42885

날짜: 2022년 1월 31일 오후 5:51

코드

https://github.com/Junroot/Algorithm/blob/main/programmers/42885.py

풀이

가장 무거운 사람부터 처리한다는 생각으로 접근했다. 무인도에 남은 사람 중 가장 무거운 사람과 가장 가벼운 사람이 같이 배에 탈 수 있는지를 반복해서 비교해봤다.

왜 가장 가벼운 사람과 타는게 문제가 없는지 의문이 생길 수 있다. 예를들어 A>B>C>D 순으로 무겁다고 가정했을 때, (A, C)가 함께 탈 수 있는데 (A, D)가 함께 타면 문제가 생기지 않냐고 생각할 수도 있다. (B, D)는 함께 탈 수 있는데 (B, C)는 함께 못 타는경우가 있을 수 있기 때문이다. 하지만 이런 경우는 존재할 수 없다.

위의 가정을 식으로 표현하면 이렇게 된다.

A+D < A+C < (배의 무게 제한)

B+C < (배의 무게 제한) < B+D

따라서 A+D < B+D. 즉, A < B라는 모순이 발생하게 된다. 따라서, 가장 무거운 사람과 가장 가벼운 사람을 함께 태워도 문제가 발생하지 않는다.