[PROGRAMMERS] 구명보트(Level2)
구명보트(Level2)
-
-
문제 이해
- 주어진 수용 무게보다 작도록, 인원을 태울 수 있는 보트의 최대 개수를 구합니다.
- 이 때, 수용 가능 인원은 두명입니다.
-
알고리즘 구현
- 인원이 두명으로 제한되어있으므로, 두명이 보트에 탑승한 경우와 한명이 탑승한 경우로 나뉩니다.
- 두명이 탑승한 경우는 두 인원의 무게 합이 limit 보다 적은 경우입니다. 따라서, 두 인원을
매칭하는 기준을 고려해야합니다.
- 저는 효율적으로 매칭하는 방법은, 무게가 가장 무거운 사람과 가장 가벼운 사람을 연결해보는
것이라고 생각했습니다. 만약, 가장 가벼운 사람과 가장 가벼운 사람이 함께 보트에 탈 수 없다면,
가장 무거운 사람은 혼자 탈 수 밖에 없기 때문입니다.
- 따라서 먼저 people을 정렬하고, 가장 무거운 사람 + 가장 가벼운 사람이 limit 보다 작은
경우, 두명을 탑승 시키고 보트 한 대를 카운트하고, 가장 무거운 사람 + 가장 가벼운 사람이
limit 보다 큰 경우, 혼자 탑승하고, 보트 한 대를 카운트합니다.
-
알고리즘
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0;
int n = people.size();
int end = n - 1;
int beg = 0;
sort(people.begin(), people.end(), greater<int>());
while (beg <= end) {
if (people[beg] + people[end] <= limit) {
++beg;
--end;
answer += 1;
}
else {
++beg;
answer += 1;
}
}
return answer;
}
Author And Source
이 문제에 관하여([PROGRAMMERS] 구명보트(Level2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@yamkim/PROGRAMMERS-구명보트Level2
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
문제 이해
- 주어진 수용 무게보다 작도록, 인원을 태울 수 있는 보트의 최대 개수를 구합니다.
- 이 때, 수용 가능 인원은 두명입니다.
알고리즘 구현
- 인원이 두명으로 제한되어있으므로, 두명이 보트에 탑승한 경우와 한명이 탑승한 경우로 나뉩니다.
- 두명이 탑승한 경우는 두 인원의 무게 합이 limit 보다 적은 경우입니다. 따라서, 두 인원을
매칭하는 기준을 고려해야합니다. - 저는 효율적으로 매칭하는 방법은, 무게가 가장 무거운 사람과 가장 가벼운 사람을 연결해보는
것이라고 생각했습니다. 만약, 가장 가벼운 사람과 가장 가벼운 사람이 함께 보트에 탈 수 없다면,
가장 무거운 사람은 혼자 탈 수 밖에 없기 때문입니다. - 따라서 먼저 people을 정렬하고, 가장 무거운 사람 + 가장 가벼운 사람이 limit 보다 작은
경우, 두명을 탑승 시키고 보트 한 대를 카운트하고, 가장 무거운 사람 + 가장 가벼운 사람이
limit 보다 큰 경우, 혼자 탑승하고, 보트 한 대를 카운트합니다.
알고리즘
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0;
int n = people.size();
int end = n - 1;
int beg = 0;
sort(people.begin(), people.end(), greater<int>());
while (beg <= end) {
if (people[beg] + people[end] <= limit) {
++beg;
--end;
answer += 1;
}
else {
++beg;
answer += 1;
}
}
return answer;
}
Author And Source
이 문제에 관하여([PROGRAMMERS] 구명보트(Level2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yamkim/PROGRAMMERS-구명보트Level2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)