[그리디, 난이도 중] 프로그래머즈, 구명보트

그리디 알고리즘이기 때문에 먼저 people을 오름차순으로 정렬하였다.

본인이 첫 번째로 생각한 접근법은 단순히 체중이 가벼운 순으로 묶는 방법이었다.

50 50 70 80 이 주어졌다면, (50,50),(70),(80) 총 3개의 보트로 테스트 케이스와 일치

50 70 80 이 주어졌다면, (50),(70),(80) 총 3개의 보트 테스트 케이스와 일치

그러나 이 접근법은 5 10 90 95 라는 반례와 막히게 된다.

이 경우에는 내 첫 번째 접근법으로는 답이 3이 나오는데, (5,95),(10,90) 총 2개의 보트로도 가능한 것이다.

 

정답처리된 본인의 두 번째 접근법은 무게가 가장 가벼운 사람과 가장 무거운 사람끼리 보트에 태우는 것이다.

단, 이 둘의 합이 무게 제한을 넘어갔을 경우에는 무거운 사람 한명만 보트에 태우고 그 다음으로 무거운 사람과 매칭시키는 과정을 반복한다.

매칭된 둘의 합이 제한 무게 안쪽이라면 둘다 보트에 태우고, 기준점을 그 다음으로 가벼운 사람과 그 다음으로 무거운 사람으로 잡는다.

마지막으로, 한명만 남은 상태라면 그 사람만 보트에 태우면 끝나기 때문에 answer+1를 최종적으로 리턴하면 된다.

 

 

정확성, 효율성 모두 만점

 

 

2021-11-27일 더 쉬운 코드로 재풀이하여 수정함

#include <vector>
#include <algorithm>
using namespace std;
int s,e,t;
int solution(vector<int> people, int limit) {
    sort(people.begin(),people.end());
    int answer = 0;
    s=0; e=people.size()-1;
    while(s<=e){
        if(s==e) return ++answer;
        t=people[e];
        if(t+people[s]<=limit) s++;
        e--; answer++;
    }
    return answer;
}