프로그래머스 구명보트

문제

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42885#

풀이

사람들의 무게가 들어있는 배열을 정렬한다음 최소와 최대값을 비교하여 limit가 넘지않는다면 answer(배)를 1 증가시키고 최소값도 1증가 시켜 다음 최소값을 사용하도록 한다.

그외의 경우는 이미 최소값과 더했을 떄 배에 태울 수 없는 경우기 때문에 최대값에 해당하는 사람을 태우게되므로 answer을 1증가시킨다.

for문을 빠져나왔을 때 i와 j가 같다면 남는 1명을 태우기위해 answer을 1증가시키도록 한다.

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

using namespace std;

int solution(vector<int> people, int limit) 
{
	int answer = 0;

	sort(people.begin(), people.end());

	int size = people.size();
	int i = 0;
	int j = 0;

	for (i = size-1; i > j; i--)
	{
		if ( people[i] + people[j] <= limit)
		{
			j++;
			answer++;	
		}
		else
		{
			answer++;
		}				
	}
	if (i == j)
	{
		answer++;
	}

	return answer;
}

int main()
{
	vector<int> p;
	p.push_back(50);
	p.push_back(50);
	p.push_back(50);
	p.push_back(50);

	cout << solution(p, 100);

}