[PG] 구명보트 [C++]

 

프로그래머스

 

 

구명보트에 최대 2명만 탈 수 있다는 조건 덕분에 그리디를 잘 못 푸는 나도 빠르게 해결할 수 있었다.

 

구명보트 수를 줄이고 싶다면 최대한 2명씩 묶어서 탈출시켜야 한다.

무거운 사람을 최대한 가벼운 사람들과 매칭시키면 무거운 사람이 혼자 타서 탈출하는 경우를 줄일 수 있을 것이라 생각했다.

 

몸무게 오름차순으로 정렬한 후, 양 끝을 나타내는 인덱스(left, right)를 만들고 좁혀가며 보트의 수를 세자.

두 사람의 몸무게 합이 제한보다 크다면 무거운 사람이 혼자 타도록 하고 right만 감소시키자.

제한보다 작다면 두 사람이 함께 타도록 하고 left를 증가, right를 감소시키자.

경우에 따라 left와 right가 같아질 수 있는데, 이 경우만 따로 체크해 주면 통과된다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    
    int left = 0, right = people.size() - 1;
    while (left <= right) {
        if (left == right) {
            answer++;
            break;
        }
        if (people[left] + people[right] > limit) {
            answer++;
            right--;
        } else {
            answer++;
            left++;
            right--;
        }
    }
    return answer;
}