[프로그래머스 42885 파이썬] 구명보트 (level 2, 그리디)

알고리즘 유형 : 그리디
풀이 참고 없이 스스로 풀었나요? : X

https://programmers.co.kr/learn/courses/30/lessons/42885?language=python3

소스 코드(파이썬)

def solution(people, limit):
    answer = 0
    people.sort()
    
    # 그리디 풀이 : 가장 무거운 사람과 가장 가벼운 사람 태우기. 합이 초과한다면 무거운 사람만 태워 보내기
    start = 0
    end = len(people) - 1
    
    while start < end:
        sum_tmp = people[start] + people[end]
        if sum_tmp <= limit:
            start += 1
        
        end -= 1
        answer += 1
    
    # 마지막 쯤 한 명이 남거나 모두가 구조되는 경우가 있다. 전자는 세 명에서 두 명이 구조됐거나, 두 명에서 합이 초과하여 한 명만 구조된 경우이고, 후자는 두 명 또는 한 명이 남았을 때 한번에 모두 구조된 경우이다.
    # 전자의 경우 start == end인 상태로 while이 끝나므로 조건문을 통해 1 더해준다.
    if start == end:
        answer += 1
    
    return answer

풀이 요약

1. 가장 무거운 사람과 가장 가벼운 사람을 태워 보낸다. 만약 둘의 합이 초과할 경우 무거운 사람만 보낸다

2. people을 오름차순으로 정렬해놓고, 이제 while문의 임의의 단계에서 가장 무거운 사람을 보내려고 한다고 치자. 이 사람은 혼자서 갈 수도 있고, 하나를 더 태워서 갈 수도 있다.

   만약 가장 가벼운 사람을 태우고 갈 수 있다고 생각해보자. 이 경우, 만약 태우지 않고 혼자 가버린다면? 아마 다음 무거운 사람, 그렇지 않다면 그 다음 무거운 사람과 함께 타고 갈 것이다. 그런데 다음 무거운 사람은 이전의 무거운 사람보다 가볍기 때문에, 더 많은 범위의 가벼운 사람을 태우고 갈 수 있다.

   만약 두 번째 무거운 사람이 태울 수 있는 가벼운 사람이 두 명이었다면, 첫 번째 무거운 사람이 가장 가벼운 사람을 태우고 갔어도, 두 번째 무거운 사람은 자기랑 같이 타고갈 수 있는 가벼운 사람이 한 명 남았기에 보트를 하나 아낄 수 있다.

   이런 원리로 최적해를 구한다. 이 문제에서는 이 것이 곧 일반해가 된다.

배운 점, 어려웠던 점

• 보트 당 최대 2명 태울 수 있는 점을 까먹고 계속 삽질했다... 문제를 꼼꼼하게 읽고 정확하게 이해하는 독해력을 더 길러야겠다.