(C++) - 프로그래머스(고득점 kit - Greedy) : 구명보트

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

코딩테스트 연습 - 구명보트

two pointer로 구현한 문제였습니다.

 

풀이방법

 1. 사람 몸무게를 내림차순으로 정렬합니다.

 2. 구명보트를 배치합니다.

     2-1. 가장 몸무게가 무거운 사람을 l번째로 가벼운 사람은 r번째 사람으로 정의합니다.

     2-2. people[l] + peple[r] > limit이라면 몸무게 제한을 초과합니다. 이 때는 r을 옮기더라도 가장 작은수가 r이므로 어떻게든 l번째 사람과 같이 탈 수 없습니다. 따라서 l번째 사람은 혼자 타야됩니다. answer++,l++해줍니다.

     2-3. else의 경우에는 두명씩 탈 수 있으므로 answer++, r--, l++해준 후 다른 사람을 비교해줍니다.

 3. answer를 반환해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int l = 0;
    int r = people.size() - 1;
    sort(people.rbegin(), people.rend());
    while(l<=r){
        if(people[l]+people[r]>limit){
            answer++;
            l++;
        }else{
            answer++;
            r--;
            l++;
        }
    }
    return answer;
}