[Programmers] 구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

---

 

문제 해결 과정

착안

하나의 구명보트에는 최대 2 명씩 태울 수 있으므로, 구명보트를 최소로 사용하려면 가능한 한 2 명씩 탑승을 시켜야 한다. 따라서 현재 남아있는 사람을 기준으로 가장 무거운 사람을 먼저 태운 다음, 가장 가벼운 사람을 보트에 태울 수 있는지 확인하여 태울 수 있다면 같은 보트에 태우고 그렇지 않다면 새로운 보트를 준비한다.

* 가장 무거운 사람이 타고 남는 공간에 가장 가벼운 사람을 탈 수 없다면 그 다음으로 가벼운 사람도 못 타기 때문.

 

구현

무인도에 갇혀있는 사람들의 무게가 (동적)배열 형태로 주어지면, 무게를 내림차순으로 정렬한 다음 가장 가벼운 사람(정렬된 배열의 마지막 요소)을 가리키는 인덱스를 변수에 저장한다. 반복문을 통해 앞의 사람부터 보트에 태우고, 이때 가장 가벼운 사람도 보트에 함께 탑승시킬 수 있는 경우에는 같은 보트를 사용해 무인도를 탈출시킬 수 있으므로, 가장 가벼운 사람을 가리키던 인덱스를 1 감소시킨다.

 

이와 같이 반복문을 구현하면, 앞에서부터 증가하는 인덱스와 뒤에서부터 감소하는 인덱스가 교차하는 경우 또는 두 인덱스가 같아지는 경우(마지막에 한 사람만 남은 경우) 반복문을 종료해야하는 것에 유의하면 문제를 해결할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit)
{
    int answer = 0;
    sort(people.begin(), people.end(), greater<>());
    
    int r = people.size() - 1;
    for (int f = 0; f <= r; f++)
    {
        answer++;
        if (f == r)
            break;
        
        if (people[f] + people[r] <= limit)
            r--;
    }
    
    return answer;
}

 

실행 결과