(프로그래머스 c++)구명보트

탐욕법으로 문제를 풀어야 한다.

우선 front와 back을 선언하여 각각 0, people.size() - 1을 대입한다.

while문을 통해 front <= back 동안 반복한다.

 

문제 접근법을 생각해 보자.

예시를 들어

people[70, 50, 80, 50], limit = 100 으로 들어왔다고 하자.

오름차순으로 정렬하면

50 50 70 80 이 된다.

 

front = 0(people[0] = 50), back = 3(people[3] = 80)이 된다.

front와 back 인덱스에 위치한 수를 더하여 limit보다 작거나 같은지 검사한다.

만약 두 합이 limit보다 작거나 같다면 1개의 보트에 2명이 탈 수 있다는 뜻이다.

그래서 answer++을 해주고 각각의 인덱스의 위치를 +1, -1 해주도록 한다.

 

하지만 현재 people[0] 과 people[3] 의 합은 100보다 크므로

둘 중에서 무거운 사람부터 내보내고 answer++을 해준다.

그리고 back의 위치를 -1 하여 다음 사람을 체크한다.

 

다음 순서는 front = 0, back = 2.

people[0] + people[2] 또한 100이 넘으므로

answer++, back--.

 

마지막으로 front = 0, back = 1.

people[0] + people[1] = 100 <= limit(100) 이 성립하므로

front++, back--, answer++을 실행한다.

 

그러면 front = 1, back = 0이 되므로 while문을 탈출하고 답을 리턴하게 된다..!

탐욕법으로 가장 큰 값과 가장 작은 값을 비교하여 푸는 방식으로 접근하면 된다...!

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int front = 0, back = people.size() - 1;
    
    sort(people.begin(), people.end());
    
    while(front <= back)
    {
        if(people[front] + people[back] <= limit)
        {
            answer++;
            front++;
            back--;
        }
        else
        {
            back--;
            answer++;
        }
    }
    return answer;
}