프로그래머스 구명보트 (C++)

1. 문제설명

 

2. 문제해결

전형적인 그리디 문제이다. 정렬을 하고 처음 인덱스와 마지막 인덱스를 더했을 때 limit 이하라면, 그것이 최적의 수임을 보장한다는 사실을 알면 어렵지않게 풀 수 있다. 순간 answer 개수를 어떻게 세야 할 지 모르겠어서 전체 길이 (다들 따로 타는 최악의 수)로 답을 초기화하고, 두명이 탈 때마다 하나씩 빼는 식으로 개수를 세었다. 

3. 코드

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

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