[프로그래머스 lv2] 구명보트 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

무게 제한이 limit인 구명보트에 가능한 많은 사람들을 타게 하려면, 가장 무거운 사람과 가장 가벼운 사람이 같이 타야 한다. 

 

people을 오름차순으로 정렬했을 때, 0번부터 오른쪽으로 이동하는 인덱스를 l, 마지막원소부터 왼쪽으로 이동하는 인덱스를 r 이라고 하자. 

 

people[l]+people[r]이 limit 보다 작거나 같다면 두 사람은 한 보트에 탈 수 있는 것이므로 l과 r을 각각의 방향으로 1씩 움직인다.

두 무게의 합이 limit 보다 크다면 두 사람은 한 보트에 탈 수 없는 것이므로 더 무거운 people[r]만 보트에 넣는다고 생각하고 r만 1 감소시킨다.

 

l이 r보다 작을 때까지 위의 과정을 반복한 후, l과 r이 같다면 남는 사람이 1명 있다는 의미이므로 필요한 보트의 개수를 1 증가시킨다.

최종적으로 구한 보트의 개수를 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(vector<int> people, int limit) {

    sort(people.begin(), people.end());

    int l = 0, r = people.size()-1, cnt = 0;
    while (l < r) {
        if (people[l]+people[r] <= limit) l++;
        r--;
        cnt++;
    }

    if (l == r) cnt++;
    return cnt;
}