[프로그래머스] 구명보트

링크

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

프로그래머스

풀이

모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 구하는 문제이다.

 

먼저 구명보트를 효율적으로 이용하여 사람을 구출하는 방법을 생각해야 되는데

효율적인 방법은 구명보트가 수용 가능한 무게에 최대한 가깝게 사람을 태우면 된다.

 

어떻게 해야 효율적인 무게를 찾을 수 있을까

 

저는 사람들의 무게를 오름차순으로 정렬을 하고

무게가 가장 작은 사람과 무게가 가장 큰 사람을 함께 보트에 태울 수 있는지를 확인하였습니다.

 

무게가 가장 큰 사람과 무게가 가장 작은 사람과 함께 보트를 탈 수 없다면 무게가 가장 큰사람은

무조건 혼자 탈 수밖에 없습니다.

 

이걸 이용하여 둘이 같이 탈 수 있다면 둘이 한 보트를 태우게 하고

만약에 같이 못 탄다면 무게가 큰 사람만 혼자 보트를 타도록 하였습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010
const int INF = 2000000000;

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
int solution(vector<int> people, int limit) {
	sort(people.begin(), people.end());

	int left = 0, right = people.size() - 1;

	int answer = 0;
	while (left <= right) {
		if (left == right) {
			answer++;
			break;
		}
		if (people[left] + people[right] <= limit) {
			answer++;
			left++; right--;
		}
		else {
			answer++;
			right--;
		}
	}
	return answer;
}

 

궁금하신 거나 잘못된 점이 있다면 과감히 댓글 남겨주세요 ㅎ