구명보트

처음 문제를 보고 생각한건, 무게 제한을 만족하는 최대 인원 수가 최적해라고 생각하여 우선순위 큐를 사용하여 가장 작은 무게를 가진 사람부터 빼내는 방법을 사용했지만 오답이라고 나왔다. 왜냐하면 구명보트의 인원 제한이 2명이라는걸 인지하지 못했다.

다른 코드를 참고해본 결과, 무게 제한에 가장 근접하면서도 인원 제한을 만족하는 원소들이 최적해라는걸 알았다.

이해를 돕기 위해 예를 들어보겠다.

무게제한 : 100

[30, 40, 50, 60]

무게가 가장 작은 인원부터 빼내면 횟수가 3번이지만 (30, 40), (50), (60)

무게 제한에 가장 근접하게 빼내면 2번이다! (30, 60), (40, 50)

이 점에서 Greedy의 특성이 나타난걸 알 수 있다.

 

또한 탐색 범위를 효과적으로 줄이기 위해 투포인터 방식을 사용했다.

정답코드

#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 l = 0, r = people.size() - 1;
	//무게 제한에 가장 근접한 답이 local optimal solution
	while (l <= r) {
		if (people[l] + people[r] <= limit)
			l++;
		r--;
		answer++;
	}
	return answer;
}