[프로그래머스] 구명보트 c++ 코드 및 풀이

문제 링크

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

프로그래머스

 

문제 

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

people                                                                                                                  limit                                     return

[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

 

코드 및 풀이

이 문제는 간단하게 최대 두명! 이라는 선택지가 주어졌기 때문에 가장 높은 사람과 가장 낮은 사람의 조합을 진행을 하면 된다고 생각합니다. 

 

그것이 가능하다면 보트의 갯수 두개를 합해 limit보다 작다면 i++,answer++을 진행을 하고

합이 limit보다 크다면 answer++을 진행하였습니다.

 

vector의 크기를 줄여주면서 인덱스와 같게되는 시점에는 모든 인원이 보트에 탄것이므로 반복문을 종료하는 그리디 알고리즘을 진행하였습니다.

/*

한번에 최대 2명씩 밖에 탈 수없고 무게 제한이 있음

구명보트를 최대한 적게 모든 사람을 구출

우선 sort를 통해 내림차순으로 정렬을 진행

어차피 최대 2명이 탈 수 있는것이기 때문에 우리는 가장 높은사람과 가장 낮은 사람과의 비교를 통해

조합이 가능하다면 ++ 아니라면 한명씩 태우는 방식을 진행하면 된다고 생각.

*/

#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 i = 0;

    while (i < people.size()){

        int biggest = people.back(); // 가장 몸무게가 큰 사람과 낮은 사람들의 조합

        people.pop_back();

        if(people[i] + biggest <= limit){

            answer++;

            i++;

        }

        else

            answer++;

    }

    return answer;

}