[알고리즘문제] 프로그래머스 - 구명보트

문제 자체는 간단하다. 구명보트에는 2명만 탈 수 있고, 무게 제한이 주어질때 필요한 최소한의 보트수를 구하는 문제이다. 전형적인 그리디 문제이다.

 

처음 생각한 방법은,

가벼운 사람들 먼저 태워서 보내는 방법이다. 이를 위해 최소힙을 사용하였다. 근데 구현을 하다보니, 생각보다 세세하게 신경써줘야 하는 부분이 많았고 최대 2명밖에 탈 수 없다는 조건을 늦게 봤다. 

 

두번째로 생각한 방법은,

무거운 사람과 가벼운 사람을 적절히 조합해서 태우는 방법이다. 2명을 태우는데 20,10을 태우는 것보다는 90,10을 태우는 것이 훨씬 이득이기 때문이다. 

 

무거운쪽 인덱스를 가리키는 e(people.size()-1), 가벼운쪽 인덱스를 가리키는 s로 나누었다.

people[s] + people[e] >=limit  --> true : 두 사람을 태울 수 있다, false : 한 사람만 태울 수 있다.

여기서 true인 경우는 두 사람을 모두 태웠기 때문에 s와e의 값을 하나씩 빼주고, 한 사람만 태울 수 있는 경우는 e만 하나 빼준다.

 

위의 과정은 s<=e가 참일 때까지 반복하게 된다.

 

#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 s = 0;
    int e = people.size()-1;
    
    while(s <= e){
        if(people[e] + people[s] <= limit){
            s++;
            e--;
        }else{
            e--;
        }
        answer++;
    }
    return answer;
}