프로그래머스 구명보트 C++

문제설명

 

 

제한사항

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

입출력 예

people                                                                                                                          limit                                 return

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

 

 

=> 탐욕법으로 문제를 해결해야 합니다. 

=> 2명만 보트에 탈 수 있다는 것을 염두에 둬야합니다. 

=> 가장 무거운 사람을 limit에서 뺀 후, 남은 사람중 가장 가벼운 사람을 뺄 수 있는지 확인합니다. 

=> 가장 가벼운 사람을 뺄 수 있다면 limit에서 뺍니다. 

=> 위의 알고리즘을 실행하며 뺀 사람의 수가 people의 수와 같다면 while문에서 탈출합니다. 

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<int> people, int limit) {
    int boat = 0;
    
    sort(people.begin(), people.end()); //오름차순

    int sIndex=0 , cnt=0; //시작인덱스, 탄사람수, 보트갯수
    int eIndex =1; //끝인덱스
    while(1)
    {
        int eWeight = people[people.size()-eIndex++];//가장 무거운 사람 무게 
        cnt++;
        if(limit-eWeight >= people[sIndex])
        {
            cnt++;
            sIndex++;
        }
        boat++;
        if(cnt >= people.size()) break;
    }
    
    return boat;
}