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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

문제의 핵심 포인트는 한 번에 최대 2명만 탈 수 있다는 것이다. 직관적으로 생각하면 가장 무거운 사람과 가장 가벼운 사람이 퇴면 된다는 생각이 들 것이다. 그대로 구현해주면 된다. people 배열을 정렬한 후 앞에서 시작하는 인덱스를 light, 뒤에서 시작하는 인덱스를 heavy라고 하자. 그렇게 하면 people[light] + people[heavy] <= limit 인 경우에는 보트를 탈 수 있다는 것이므로 정답을 1 증가시키고 light를 1 증가, heavy를 1 감소시켜준다. people[light] + people[heavy] > limit 인 경우에는 people[heavy] 혼자서 보트를 타야하므로 정답을 1 증가시키고 heavy를 1 감소시킨다. 이런 과정을 light <= heavy가 될 때까지 반복하면 된다.

코드

#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 light = 0;
    int heavy = people.size() - 1;
    while (light <= heavy ) {
        if (people[light] + people[heavy] <= limit) light++;
        answer++;
        heavy--;
    }
    return answer;
}