구명보트
풀이과정
- 구명보트의 최대 탑승인원이 2명이므로 구명보트를 가장 적게 쓰려면 가능한 2명씩 보트를 태우도록 해야한다. 무게 제한이 넘지 않는 선에서 가장 무거운 사람과 가장 가벼운 사람을 같이 태워야 남은 사람들이 2명씩 보트를 탈 수 있는 확률이 높아진다. 가장 무거운 사람과 가장 가벼운 사람의 무게 합이 무게 제한을 넘으면 가장 무거운 사람은 혼자 보트에 태우고 그 다음으로 무거운 사람과 가장 가벼운 사람을 같이 태울 수 있는지 따져본다. 가장 가벼운 사람과 탈 수 있는 가장 무거운 사람을 구해 2명을 보트에 태우고나면 그 다음으로 가벼운 사람과 탈 사람을 구한다. 2명이 탈 수 있는 경우가 있을 때까지 이 과정을 반복한다.
- people 리스트를 내림차순으로 정렬한다.
- start 변수를 0으로(가장 무거운 사람), end 변수를 len(people)-1으로(가장 가벼운 사람) 초기화한다.
- start가 end보다 작을 동안 while문을 돌린다. while문에서 peoplep[start]와 people[end]의 합이 limit보다 작은지 따져본 후 작으면 answer, start에 1을 더하고 end에서는 1을 뺀다.(2명이 탑승할 배 하나 추가, 그 다음으로 무거운 사람과 그 다음으로 가벼운 사람에게 순서를 넘김) 그렇지 않으면 answer, start에만 1을 더한다.(1명이 탑승할 배 하나 추가, 그 다음 무거운 사람에게 순서를 넘김)
- while문이 끝나면 짝을 구하지 못한 사람의 수만큼 answer에 더한다.
Python Code
def solution(people, limit):
answer = 0
people.sort(reverse = True)
start = 0
end = len(people)-1
while start < end:
if people[start]+people[end] <= limit:
answer += 1
start += 1
end -= 1
else:
answer += 1
start += 1
answer += len(people[start:end+1])
return answer오류와 해결
처음에 구명보트의 최대인원이 2명인 것을 못 보고 그리디로 풀었더니 답이 나오지 않았다. 2명만 탈 수 있도록 수정하니 해결되었다. 알고리즘 수업 시간에 들은 바로는 최대인원이 정해져있지 않은 경우에는 그리디 알고리즘으로 근사해밖에 구할 수 없다고 한다.(통 채우기 문제)
(●⁰౪⁰●)