[Programmers/프로그래머스 lv2][C++] 구명보트

문제

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

프로그래머스 구명보트

 

문제 내용

입력으로 사람들의 몸무게 정보를 담은 배열과 구명보트의 무게 제한을 받는다.

구명보트에는 최대 2명까지 탈 수 있으며, 이때 사람들의 몸무게 합이 구명보트의 무게 제한보다 같거나 작아야 한다.

우리는 필요한 구명보트의 최솟값을 구하면 된다.

 

문제 풀이

먼저 사람들의 몸무게 정보를 담은 배열을 정렬해야 한다.

 

그리고 양쪽 끝에서부터 차례로 몸무게를 더해서 limit보다 작으면 그 둘을 한 보트에 태운다.

만약 더한 몸무게가 limit보다 큰 경우, 몸무게가 큰 쪽은 혼자 타야 한다.

몸무게가 작은 사람은, 오른쪽-1 위치의 사람과 함께 탈 수도 있겠지만, 몸무게가 큰 큰 사람은 그 어떤 사람과도 같이 탈 수 없기 때문이다. (정렬을 했기 때문에, 가장 왼쪽에 있는 사람이 가장 몸무게가 작기 때문)

 

코드

#include <algorithm>
#include <vector>

using namespace std;

int solution(vector<int> people, int limit) {
    sort(people.begin(), people.end());

    int start = 0;
    int end = people.size() - 1;
    int answer = 0;

    while (start <= end) {
        if (start == end) {
            answer++;
            break;
        }
        if (people[start] + people[end] <= limit) {
            answer++;
            start++;
            end--;
        } else { // limit를 초과했을 때
            answer++;
            end--;
        }
    }

    return answer;
}

 

문제 코드 설명

start와 end의 값이 같을 때, 해당 인덱스의 사람은 보트를 혼자 타야 하기 때문에 answer++;이 필요하다.

people[start]+people[end]의 값이 limit보다 작거나 같다면, start에 있는 사람과 end에 있는 사람이 보트에 같이 탈 수 있다는 뜻이고, answer값 조정 이후 start, end의 인덱스 값을 조정해야 한다.

people[start]+people[end]의 값이 limit보다 크다면, end에 있는 사람은 보트에 혼자 타야한다는 뜻이다. (start에 있는 사람은 end-1에 있는 사람과 같이 탈 수도 있다.) 이 경우 answer값 조정 이후 end의 인덱스만 조정하면 된다.