처음엔 문제를 제대로 안 읽고;; 구명보트에 인원제한도 있는 거를 몰랐음 그래서 일단 가벼운 애들을 최대한 꽉꽉 채워서 보냈는데…! 당연히 틀렸었음
구명보트 하나에 2명이라는 인원 제한이 있으니까 조합은 아래와 같이 나올 수 있음 (가 : 젤 가벼운 사람 무 : 젤 무거운 사람)
2명을 태우는 경우 : 가가, 가무, 무무
1명만 태우는 경우 : 가, 무
저 조합들 중에 가무, 가무가 불가능하다면 무 이렇게 순차적으로 내보내는 것이 낫다고 판단함
무무가 별로라고 판단한 이유는 무무를 보내도 어차피 나중에 가가 조합의 아주 널널한 구명보트가 생기기 때문에 굳이 조합을 그렇게 할 필요가 없다고 판단함
그래서 내가 생각한 솔루션은
사람 무게 순 정렬
가장 가벼운/무거운 사람 인덱스 각각 저장 (맨 앞 맨 끝)
그 인덱스에 해당하는 사람들 무게 합이 무게 제한 넘는지 확인
넘으면 몸무게 많은 사람만 탑승시키고 해당 인덱스 -1
안 넘으면 둘 다 탑승시키고 각각 인덱스 +1 -1
3번 과정 반복해 요렇게 보내다가 두 인덱스가 같거나 가벼운 사람의 인덱스가 더 작아지면 끄읏
ex 2명있어는 상황에 1번 2번 둘 다 태워 보낼 수 있음 → 태워 보낸 후 인덱스 변화 2 1 이므로 가벼운 사람의 인덱스가 더 작아지는 경우 생기기 가능
📖풀이
📎구현
def solution(people, limit): light, heavy = 0, len(people)-1 # 무인도에 남은 인원 중 가장 가벼운 사람 위치, 가장 무거운 사람 위치 boat = 0 # 필요한 구명보트 수 people.sort() # 몸무게 순 정렬 # 무인도에 남은 사람 있는 동안 반복 while light <= heavy: # 2명을 모두 태워 보낼 수 있는 경우 if people[light] + people[heavy] <= limit: light += 1 heavy -= 1 # 최대 1명만 태워 보낼 수 있는 경우 else: heavy -= 1 boat += 1 return boat