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

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

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

sort와 그리디 알고리즘을 사용하면 해결할 수 있는 문제입니다.

 

문제 접근법

• 보트에 탈 수 있는 인원의 최대가 2명이라는것을 생각합니다.
• 가장 베스트한 케이스는 가장 가벼운 사람과 무거운 사람이 탔을때 한계치를 넘지 않는것입니다.
• 이를 위하여 sort를 사용합니다.
• 앞과 뒤를 체크하기 위한 index 두개를 준비합니다.
• 맨 앞 인원과 맨 뒷 인원의 무게 합이 한계를 넘는지를 체크합니다.
  • 한계를 안넘을 경우 두명을 태운것이므로 앞 인덱스를 증가시키고 뒤 인덱스를 감소시키고 answer을 1증가시킵니다.
  • 한계를 넘을 경우 무게가 한명을 태울수 밖에 없으므로 뒤 인덱스를 감소시키고 answer을 1증가시킵니다.
• 위 과정을 앞 인덱스가 뒤 인덱스보다 작을동안 진행합니다.

아래는 코드입니다.

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> people, int limit) {
    int answer = 0;
    int a = 0, b = people.size();
    
    sort(people.begin(), people.end());
    
    if(b == 1)
        return answer = 1;
    
    while(a < b)
    {
        if(people[a] + people[b - 1] <= limit) 
            a++;
        
        answer++;
        b--;
    }
    
    return answer;
}