[프로그래머스] (그리디) 구명보트 c++

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

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

 

기본적인 아이디어.

 

모든 사람을 다 구해야하므로

1. 구명보트에는 몸무게가 많이 나가는 사람을 한명 태운다음

2. 1번의 구명보트 남은 자리에 몸무게가 작은사람순으로 무게제한에 도달하기 전 까지 사람들을 태움.

3. 다 구출할때 까지 1번 과정을 반복해야 최소한의 구명보트로 사람들을 구출할 수 있다.

 

 

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool cmp(int x, int y)
{
    return x>y;
}

//https://programmers.co.kr/learn/courses/30/lessons/42885
int solution(vector<int> people, int limit) {
    int answer = 0;
    int fi=people.size()-1;
    int cnt=0;
    int kg;
    
    sort(people.begin(),people.end(),cmp);
    
    for(answer=0; answer<people.size(); answer++)
    {
        cnt++;
        kg=limit-people[answer];
        
        
        while(1)
        {
            if(cnt==people.size()) break;
            
            if(kg-people[fi]>=0)
            {
                kg=kg-people[fi];
                fi--;
                cnt++;
            }
            else
            {
                break;
            }
        }
        
        if(cnt==people.size()) 
        {
           break;             
        }
    }
    
    return answer+1;
}