프로그래머스/고득점문제키트/탐욕법(Greedy)/구명보트

 

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    int light_idx = 0;
    int heavy_idx = people.size()-1;
    int double_cnt = 0;
    
    //light_idx 가 heavy_idx와 같아지는 순간은 나오도록 한다.
    //어차피 double_cnt 만 헤아리면 되기 때문이다.
    while (light_idx < heavy_idx){
        if(people[light_idx]+people[heavy_idx]<=limit){
            light_idx++;
            heavy_idx--;
            double_cnt++;
        }
        else{
            heavy_idx--;
        }
    }
    answer = people.size() - double_cnt;
    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/42885

알고리즘 연습 - 구명보트 | 프로그래머스

핵심 조건만 정리하면, 구명 보트 한 턴 당 max 2명 태울 수 있다는 점이다.

가장 효율적으로 태우기 위해서 이렇게 생각해볼 수 있다. 

가장 가벼운 사람 pick, 가장 무거운 사람 pick 한 후 둘의 합이 limit 내에 들어가는 경우(즉, 둘을 한 번에 태울 수 있는 경우),

둘을 태우고, 만약에 그렇지 않은 경우(이 둘의 합이 limit을 초과하는 경우), 가장 무거운 사람만 태운다. 

이를 코드로 구현하면 된다.

이를 구현하기 위해선 people 몸무게 벡터를 sort한 뒤, 아래와 같이 가벼운쪽 idx, 무거운 쪽 idx를 설정 후 좌우에서 서로 만날때까지 진행한다.

한가지 요령은 둘을 한 번에 태우는 경우에 대해서만 잘 count 한 뒤, 전체 인원수에서 둘을 한번에 태우는 경우의 수만 빼준다면 보트의 승선 횟수가 될 것이다. 

 

[구현 코드]

---