Programmers : 구명보트

풀이 요약

투포인터

풀이 상세

1. 문제에서의 최적해는 현재 나가지 않은 사람들 가운데 가장 가벼운 사람과 함께 나갈 수 있는 가장 무거운 사람을 찾아 둘이 함께 보트를 타게 하는 경우이다.

2. 먼저 오름차순 정렬을 해준 후, $l$ 을 가벼운 사람, $r$ 을 무거운 사람을 가리키도록 하여, $l$ + $r$ 을 더한 값이 $limit$ 안에 들어온다면 $l$, $r$ 두 좌표를 모두 업데이트 하고, 그렇지 않은 경우는 $r$ 의 값만 업데이트 해주면 정답에 도달한다.

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