Greedy, 구명보드

안녕하세요.

최근에 알고리즘 공부를 다시 시작했는데, 다시 시작한 김에 C++ 로 언어를 바꿔보았습니다.

확실히 코딩하는 시간이나 습득하는 시간 등 장점이 많다고 느꼈어요.

 

지인 분들이 왜 python으로 안하냐고들 하는데

그러게요 ... 마지막 욕심일지두 희희

 

오늘은 프로그래머스의 Greedy 문제인 구명보드를 풀어보고자 합니다.

참고로 Greedy는 지난 포스팅에서 개념을 확인할 수 있습니다.

 

일단 문제는 아래와 같습니다.

 

 

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다.
구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.


제한사항

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

입출력 예

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

 

이 문제를 보고 knapsack 알고리즘이 생각나서 다시 한 번 공부해보고 왔어요.

Greedy 알고리즘을 배울 때 한 번쯤 들어보는 knapsack...

 

이 문제를 어떻게 풀었냐면, 일단 최대 2명이 탈 수 있습니다. 

이 부분이 문제를 아주 쉽게 만들어줬다고 생각하는데요.

1명아니면 2명만 탈 수 있는거죠.

 

일단, 몸무게 순으로 people 배열을 정렬합니다. 

이 때 c++ 에서 지원하는 헤더 중에 alogorithm의 sort 함수를 사용했어요.

 

그리고 무거운 사람 기준으로 가장 가벼운 사람과 배를 탈 수 있으면 묶어서 내보내고, 아니면 혼자 내보내는 것입니다.

 

 

코드는 아래와 같습니다.

 

 

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
        sort(people.begin(), people.end());
    reverse(people.begin(), people.end());
    int N = (int)people.size();
    int res = 0;
    for (int i = 0, j = N - 1; i <= j; i++) {
        if (people[i] + people[j] <= limit) {
            j--;
        }
        res++;
    }
    return res;
}

 

 

생각보다 간단하죠 ? 

오늘부터 알고리즘 공부를 열심히 ... .할거라 ... 많이 올라올 예정이에요 ㅎㅎ