문제

문제링크

나의 코드

def solution(people, limit):
    answer = 0
    people.sort()
    p1 = 0
    p2 = len(people) - 1
    
    while p1 <= p2:
        if people[p1] + people[p2] <= limit:
            answer += 1
            p1 += 1
            p2 -= 1
        else:
            answer += 1
            p2 -= 1
    
    return answer

푼 방법

투포인터를 이용해서 풀었다.
투포인터를 생각해내게 된 루트는 이렇다.

먼저 보트를 최소한을 이용하기 위해선 보트를 꽉 채워야 한다.
덧붙여 주어진 문제가 그리디스럽기 때문에 정렬한 뒤에 접근해야 하지 않을까 생각했다.
그리하여 정렬된 상태에서 보트를 꽉 채울 수 있는 방법은 아래와 같았다.

1. 큰 몸무게 + 작은 몸무게 조합
2. 작은 몸무게 + 그 다음으로 작은 몸무게
3. 큰 몸무게

위와 같은 세 가지 경우를 우선순위로 하여 보트를 보낼 때 최소한으로 보트를 사용할 수 있다.

이것은 limit이 10일 때, 3, 3, 7, 7의 경우를 생각해보면 추론해내기 쉽다.

먼저 그냥 순서대로 짝 지어서 보내면

1. 3, 3
2. 7
3. 7

이렇게 세 번 보내야 한다.

그런데 큰 몸무게와 작은 몸무게를 조합해서 보내면

1. 3, 7
2. 3, 7

위와 같이 2번으로 경우를 줄일 수 있으며 이것이 최소한으로 보트를 쓴 경우이다.

즉, 일반적으로 "작은 몸무게 + 그 다음으로 작은 몸무게"의 방법론을 생각해낼 수 있지만, 위의 사례를 통해서 "큰 몸무게 + 작은 몸무게 조합"이 더 우선되어야 하는 경우임을 파악했다. 그렇다면 만약에 위의 두 경우를 모두 만족하지 않는다면 어떻게 처리해야 할까 생각하면 "큰 몸무게"라는 마지막 경우를 생각해낼 수 있다. 이는 결국 "작은 몸무게" 또는 "큰 몸무게" 둘 중 하나를 선택해야 한다고 했을 때를 가정해보면 "큰 몸무게"를 마지막 최후위의 경우로 둘 수 있음을 추론해낼 수 있다. 만약에 작은 몸무게를 보낸다면, "큰 몸무게 + 작은 몸무게 조합"이 경우를 놓칠 수 있기 때문에 작은 몸무게인 사람은 귀하다. 그렇기 때문에 큰 몸무게인 사람을 보내야 한다.