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

프로그래머스의 구명보트(Lv2) 문제이다.

 

[ 문제풀이 ]

무게제한이 있는 구명보트에 2명씩 탈 수 있을 때, 필요한 구명보트의 최소 갯수를 구해야 하는 문제이다.

 

#1. 짝 짓기

먼저, 구명보트에 사람을 2명씩 태운다고 가정했을 때, 어떻게 2명을 태우는 것이 구명보트의 갯수를 최소화 시킬 수 있는지 한번 알아보자. 한 가지 예시를 가지고 진행해보자.

(문제에서 조건으로, 사람의 몸무게는 40kg이상이라고 하였지만, 이를 배제하고 진행하겠습니다. 결론을 도출하는 과정에 있어서는 차이가 없습니다.)

구명보트의 제한무게 = 100kg

사람들의 몸무게 = [ 10 , 20 , 50 , 80 , 90 ]

그리고 편의상, 10kg인 사람을 'A', 20kg인 사람을 'B', 50kg인 사람을 'C', 80kg인 사람을 'D', 90kg인 사람을 'E' 라고 표현해보자.

가장 먼저, A(10kg)를 구명보트에 태운다고 가정해보자. 그럼 이 때, 누구랑 같이 타는 것이 구명보트가 최소가 될 수 있을까 ??

바로 , E(90kg)와 같이 타는 것이 구명보트의 갯수를 최소화 시킬 수 있다.

왜그럴까 ?! 'E'입장에서는 'A'가 아닌 다른 사람과는 구명보트를 함께 탈 수 없다. 왜냐하면 타는 순간 구명보트의 무게제한을 넘어버리기 때문이다. 즉 ! 'A'와 'E'를 따로 태우게 되면 'E'를 위한 하나의 구명보트가 더 필요하지만, 'A'와 'E'를 같이 태우게 되면 'E'만을 위한 구명보트를 줄일 수 있게 된다.

그럼 A와 E가 함께 구명보트에 탑승을 했다고 가정해보자.

 

이제 B(20kg)을 태워보자. 누구랑 같이 타는것이 가장 이득일까 ?? 당연히 D와 같이 타는 것이 이득일 것이다.

D는 B가 아니라면 그 누구와도 함께 탈 수 없기 떄문이다. (A와 E는 이미 탑승을 했기 때문에 없는 사람 취급하겠습니다.)

즉 ! 여기서도 D 한명만을 위한 구명보트를 사용하지 않고, B와 함께 탐으로써 구명보트를 줄일 수 있는 것이다.

 

결과적으로, 다음과 같은 결론을 낼 수 있다.

"몸무게가 높은 사람일수록, 낮은 사람과 함께 타는 것이 이득"이다.

 

#2. 정답도출

우리는 몸무게가 저장되어 있는 주어진 배열 or Vector에서 어떤 사람이 몸무게가 높은지 낮은지를 알아야 한다.

이를 위해서 본인은 몸무게를 내림차순으로 정렬을 시켜주었다.

정렬을 시키게 되면, 상대적으로 앞쪽에는 몸무게가 높은 사람이 상대적으로 뒤쪽에는 몸무게가 낮은 사람이 존재하게 될 것이다.

즉 ! 주어진 사람의 수가 N명이라고 가정했을 때, 이들의 몸무게가 Vector에는 0번 Index ~ N - 1번 Index까지 저장이 되어 있을 것이다. 그래서 구명보트를 사용해 주었다.

[ 0번 Index와 N - 1번 Index ]

[ 1번 Index와 N - 2번 Index ]

[ 2번 Index와 N - 3번 Index ] ... 이런식으로 !

하지만 ! 반드시 이렇게 묶을 수 있는 것은 아니다.

구명보트의 무게제한이 100kg이고 , 가장 몸무게가 무거운 사람이 90kg, 가장 가벼운 사람이 20kg 라고 가정해보면

0번 Index에는 '90' 이 , N - 1번 Index에는 '20' 이 저장되어 있을 것이다.

이 경우에는 0번 Index와 N - 1번 Index를 묶을 수가 없다. 이는, 0번 Index에 있는 '90kg'인 사람은 그 누구와도 묶일 수가 없음을 의미한다. 왜냐하면, N - 1번 Index에 있는 사람이 가장 가벼운 사람이기 때문이다. 가장 가벼운 사람과도 묶일 수가 없는데 다른 사람과는 절대로 묶일 수가 없을 것이다. 따라서, 이 경우에는 90kg를 위한 보트를 하나 주고, 그 다음 사람으로 넘어가면 된다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> people, int limit) 
{
    int answer = 0;
    sort(people.begin(), people.end(), greater<int>());
    int Left = 0;
    int Right = people.size() - 1;
    while(Left < Right)
    {
        if(people[Left] + people[Right] <= limit)
        {
            Left++;
            Right--;
            answer++;
        }
        else
        {
            Left++;
            answer++;
        }
    }
    if(Left == Right) answer++;
    return answer;
}