[프로그래머스][그리디][C++] 구명보트

문제

프로그래머스 그리디 - 구명보트 (Level 2)

코딩테스트 연습 - 구명보트

 

---

문제 풀이

접근 방식

무게 제한이 있는 구명 보트에 최대 2명씩 태워서 구출할 때, 필요한 구명 보트 개수의 최솟값을 구하는 문제이다.

이 문제를 해결하기 위해 우선, 사람들의 무게를 오름차순으로 정렬하였다.

그 후, 가장 가벼운 사람과 가장 무거운 사람이 함께 탈 수 있는지를 확인하는 방식으로 문제를 해결하였다.

 

함께 탈 수 있다면 start 인덱스와 end 인덱스를 함께 움직여 주었고,

함께 탈 수 없다면 end 인덱스만 이동시켜서 그 다음으로 무거운 사람과 함께 탈 수 있는지를 체크해주었다.

 

---

풀이 코드 - C++

#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 start = 0;
    int end = people.size() - 1;
    while(start <= end){
        if(start - end == 1){
            answer++;
            break;
        }
        if(people[start] + people[end] <= limit)
            start++;
        end--;
        answer++;
    }
    return answer;
}

실행 결과

실행 결과 : 100.0