[Programmers] 구명보트

사담) 요새 1일 3문제 정도 알고리즘 문제 풀기를 다시 시작하고 있다.
퇴사 후에 1일 1문제 정도씩 하다가 포트폴리오 및 CS공부때문에 잠시 제쳐뒀다가 지금은 절대적인 공부량을 늘리면서 알고리즘 문제도 틈틈히 풀고있다. 아직은 레벨이 낮지만 꾸준히 해서 독보적인 사람이 되어야겠다.

구명보트 문제는 전에 풀다가 막혀서 다시 찾은 문제
탐욕법이라는 알고리즘을 이용하라는 힌트가 있다.

가장 적은 횟수로 제한 용량이 있는 구명보트를 사용해서 사람들을 옮기는 방식이며 최대 2사람까지만 태울 수 있다.

1) 처음에는 오름차순 정렬을 해서 무게가 작은 사람들끼리 태우는 방식으로 해나갔다.
반례: [10,10,50,60,70,90] limit:100일 경우
total: (10+10)+50+60+70+90 =>5
실제 최소 구명보트 횟수는 (10,90) + (10+70) + 50 + 60 =>4이다.
2명이 탄 보트가 많을 수록 최소 이동횟수가 생긴다.

따라서 첫번째 방법으로는 풀 수 없는 문제

2) 가장 가벼운 사람 + 가장 무거운 사람 끼리 태워나가는 방식
최대 인원은 2명이니 투포인터를 사용해서 문제를 해결하였다.
2번 방식으로 2명의 무게 합이 limit와 같거나 작다면 두 개의 포인터 이동 후 answer++;
무게의 합이 limit를 초과하면 무거운 사람만 태우고 (end포인터를 옮김) answer++;

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

using namespace std;

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