[프로그래머스] 42885. 구명보트

문제 링크

[프로그래머스] 42885. 구명보트

풀이 과정

위 예시에서, 처음에는 방법 ①로 문제를 해결하려고 했습니다. 하지만, 몸무게가 적은 사람부터 차례로 보트를 채워나가면 공간 낭비가 생기므로 최적이라고 볼 수가 없었습니다.

보트를 최적으로 채우기 위해서는 방법 ②처럼 몸무게가 적게나가는 사람과 많이 나가는 사람을 차례로 태워야 합니다.

while (low <= high) {
    if (people[low] + people[high] <= limit) {
        low++;
        high--;
    } else {
        high--;
    }

    answer++;
}

로직은 다음과 같습니다.

1. 몸무게가 가장 적게 나가는 사람 a와 가장 많이 나가는 사람 b를 한 배에 태울 수 있는지를 확인한다.
   • b가 남아있는 사람들 중 몸무게가 가장 적은 a와도 동승할 수 없다면, 혼자 타야 한다.
   • b가 a와 탈 수 있으면 둘을 한 배에 태운다.
2. 모든 사람을 다 태울 때까지 1을 반복한다.

코드

function solution(people, limit) {
    let answer = 0;
    let low = 0,
        high = people.length - 1;
    people.sort((a, b) => a - b);

    while (low <= high) {
        if (people[low] + people[high] <= limit) {
            low++;
            high--;
        } else {
            high--;
        }

        answer++;
    }

    return answer;
}

solution([70, 50, 80, 50], 100);
solution([70, 80, 50], 100);
solution([40, 50, 60, 70, 80, 90, 100, 110], 200);
solution([240], 240);