오늘 리뷰할 문제는 구명보트이다. 대표적인 그리디 기출문제인데, 대부분 그리디는 정렬을 먼저 하고 시작하게 된다.
1. 문제 해설
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
여기서 내가 놓쳤던 키워드는 2명까지만 탈 수 있다는 점이다.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
2. 어려운 점
일단 처음에 내가 풀었는데, 오답처리가 됐다. 어떤 부분에서 오답인지 알아내기가 어려웠다. 내가 풀었던 풀이는 다음과 같다.
def solution(people, limit):
people.sort()
cnt = 1
boat = 0
temp = limit
for person in people:
if temp<person or boat>=2:
boat = 1
cnt +=1
temp = (limit-person)
else:
temp -= person
boat +=1
return cnt블로그에서 본 풀이는 다음과 같았다. 크게 내 풀이랑 다를 바가 없는데 나는 왜 틀렸을까?
def solution(people, limit):
people.sort()
cnt =0
i =0
j =len(people)-1
while i<=j:
cnt +=1
if people[j]+people[i]<=limit:
i+=1
j -=1
return cnt나는 루프를 돌면서 limit가 넘기 전까지 하나씩 집어넣고 limit가 넘거나 보트에 2명이상 들어가게 되면 cnt를 추가했다.
블로그 풀이는 while문을 돌면서 계속 cnt를 추가한다. 아...
제일 마지막(큰)원소랑 제일 작은 원소를 더해가며 비교하는 것이다.
계속 i를 계속 증가시키면서 순차적으로 작은 원소와 큰 원소를 더해 limit에 해당되는지 아닌지 점검한다.
제일 작은 것이랑 제일 큰 것을 더해서 만약 limit를 넘어가면, 제일 큰 것만 보트에 태우고 j를 -1하게 되면, 제일 작은 것과 제일 큰것 -1 을 더해서 비교하게 된다. 이때 해당 원소들이 limit에 포함되게 되면, 그 다음 작은것으로 넘어가서
결론적으로는 전체 원소를 모두 탐색하게 된다는 것이다.
2-1. 그렇다면, 왜 내가 풀었던 풀이는 틀린 답이 나오는 걸까?
예를들어 이런 케이스를 생각해보자.
[10,10,10,90,90,90] 이런 경우가 있다.
이런 경우에는 보트는 총 3개가 필요한데, 내가 풀이한 방법으로는 4개가 나온다.
나의 방법으로는 가장 극단적인 비교가 안되기 때문이다.
여기서 극단적인 것의 의미는 가장 큰것과 가장 작은것을 집어넣어 최대의 효율을 내는 것이다.
2-2. 왜 이렇게밖에 풀 수 없는건가?
왜냐면 보트의 제한 인원이 2명이기 때문이다. 2명으로 고정할 경우, 가장 작은 원소와 가장 큰 원소를 더해 비교하는 식으로 하게 되면 가장 극단적이고 명확한 비교가 가능하기 때문이다.
3. 안보고 풀어보기
풀이 완료!!
def solution(people, limit):
people.sort()
i =0
j = len(people)-1
cnt =0
while i<=j:
cnt +=1
if people[i]+people[j]<=limit:
i +=1
j -=1
return cnt큰 사람부터 태우되, 작은 사람도 낄 수 있으면 낀다.
