Posted Dec 17, 2020 2020-12-17T20:00:00+09:00 by Daekyo Jeong
Updated Apr 13 2021-04-13T19:23:19+09:00
문제
구명보트
접근
이 문제에서 가장 중요한 것은 최대 탑승인원이 2명이라는 것이다.
가장 무거운 사람을 태우고, 남은 한자리에 태울 수 있는 사람이 있다면 누굴 태우든 상관이 없어진다.
최대 무게에 딱 맞출 필요가 없다는 것이다.
2명을 태우는 것에만 집중하면 된다.
역순으로 정렬하고 가장 무거운 사람을 태우고, 가장 가벼운 사람을 태울 수 있다면 함께 태우고, 불가능하면 혼자타면 된다.
예를 들어 [50, 40, 20, 10] 이 있다면, 50과 함께 태울 사람을 고르는데 시간을 쓰지말고, 가장 뒤에 있는 10만 검사해준다.
코드
1
2
3
4
5
6
7
8
| def solution(people, limit):
answer = 0
people.sort(reverse = True)
for p in people:
if p+people[-1] <= limit:
people.pop(-1)
answer +=1
return answer
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0;
int size = people.size();
int i = 0;
sort(people.begin(), people.end(), greater());
while(size > i){
if(people[i] + people[size-1] <= limit){
size--;
}
i++;
answer++;
}
return answer;
}
|
