[프로그래머스 고득점 kit] 구명보트 c++ (greedy)

문제 링크

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

프로그래머스

 

문제 풀이

어렵게 생각할 필요 없다. 가장 무게가 많이 나가는 사람 ( == 가장 제한된 합승 조건을 가진 사람) 부터 최대한 사람을 많이탑승 시키면 정답이 나온다.

이를 구현하기 위해 Sort를 진행한 뒤, back에서부터(가장 높은 무게의 사람) 최대한 많은 사람과 합습 시키기위해 가장 무게가 적게 나가는 순서대로 합승 시킨다.( Sort 했기에 역시 Front 부터 쭉)

 

 

정답 코드

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

    return answer;
}

//80 70 50 50
//80 <> 50 x
//100  1 2 3 4,,,, 8

//90 89  10 1

//90 70  30 10
// 50 50 10 20 20
//제일 무거운 사람부터 가장 많은 사람과 탈 수 있게.( 같은 수면 무거운 사람을 포함)
//