[프로그래머스 lv 2 ] - 구명보트 (C++)

 

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

프로그래머스

 

풀이 : 우선 오름차이 정렬을 한뒤 좀 헤매긴했다 순차적으로 i +( i+1 ) 식으로 처음에 계산했다가 왜 안되는지 반례를 찾아 본뒤에야 해결 했다.

 

 

예를 들어,

people = [10, 20, 30, 40, 50, 60, 70, 80, 90]
limit = 100

이 같은 경우 처음에 생각 했던 방식으로는 10,20 / 30,40 / 50 / 60 / 70 / 80 / 90 으로하면 답이 7이 나오는데 제일 큰수와 제일 작은수를 더하는 식으로 하면 10,90 / 20,80 / 30,70 / 40,60 / 50으로 되어 5 라는 값이 나와서 7보다 더 효율적으로 탑승 해줄 수가 있다.

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int front = 0;    
    int back = people.size()-1;      

    sort(people.begin(),people.end());
    
    int i=0;
    
    while(front <= back)
    {
        if(people[front] + people[back] <= limit)
        {
            front++;
            back--;
        }else
        {
            back--;
        }
        
        answer++;
    }

    return answer;
}