Programmers Level 2: 구명보트(C++)

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

코딩테스트 연습 - 구명보트

풀이법

1) Greedy 방식을 사용해서 해결하는 문제였다.

2) 사람들의 무게인 people 배열을 오름차순으로 정렬 후, 가장 몸무게가 많이 나가는 사람 부터 보트에 태웠다. 이후 몸무게가 다음으로 많이 나가는 사람이 보트에 들어갈 수 있으면 반복하며 태워주었고, 불 가능할 경우 가장 가벼운 사람, 그 다음으로 가벼운 사람을 넣는 방식의 이분 탐색적인 방식을 활용하여 문제를 해결할 수 있었다.

3) Greedy 접근법이라는 것을 알고 풀었기에 더 쉽게 풀 수 있었던 문제라고 생각한다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(int a, int b)
{
    return a>b;
}

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(),people.end());//작은 순 정렬
    int start=0;
    int end=people.size()-1;
    while(start<=end)
    {
        int nowW=people[end];
        end--;//하나 줄이기;
        while(nowW+people[end]<=limit)
        {
            nowW+=people[end];
            end--;
        }
        while(nowW+people[start]<=limit)
        {
            nowW+=people[start];
            start++;
        }
        answer++;
    }
    return answer;
}