구명보트

작성일 | In

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

문제 링크

탑승 인원과 무게가 제한된 구명보트를 최소한으로 사용하여 승객을 모두 구출하는 문제이다.
제한 인원은 최대 2명이고, 제한 무게는 주어진다.

가장 적은 구명보트를 사용하려면, 구명보트 하나를 사용할 때 최대한 제한 무게에 가깝게 사람들을 묶어 탑승시켜야 한다.
무게에 제한이 있으므로, 무거운 사람들을 어떻게 태울 것인가가 문제의 핵심 포인트라고 생각했다.
가벼운 사람들을 먼저 구명보트에 태우면, 후에 무거운 사람들을 태울 때 구명보트에 낭비되는(사람을 태울 수 있는) 무게가 존재할 수 있음에서 힌트를 얻었다.
따라서 가장 무거운 사람을 먼저 태우고, 그 남는 무게에 가장 가벼운 사람이 탑승할 수 있는지 확인하는 방법으로 문제를 해결했다. 이 문제에서 제한 인원이 최대 2명이기 때문에 가장 무거운 사람과 가장 가벼운 사람만 확인하는 방법으로도 문제 해결이 가능했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> people, int limit) {
    sort(people.begin(), people.end());
    int boat=0;
    int frontIdx=0, backIdx=people.size()-1;
    while(frontIdx <= backIdx) {
        if(frontIdx != backIdx) {
            if(people[backIdx] + people[frontIdx] <= limit)
                ++frontIdx;
        }
        --backIdx;
        ++boat;
    }
    return boat;
}

int main(void) {
    int n;
    scanf("%d", &n);

    vector<int> weights(n);
    for(int i=0; i<n; ++i) {
        int weight;
        scanf("%d", &weight);
        weights[i] = weight;
    }

    int limit;
    scanf("%d", &limit);

    printf("%d", solution(weights, limit));
}
0%