C++ 프로그래머스 구명보트

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

프로그래머스

풀이

일단 조건을 잘 봐야한다. 

1. 구명보트는 최대 2명밖에 탈 수 없다.

2. 구명보트는 작아서 무게제한이 있다.

 

조건에 맞춰서 먼저 people벡터를 오름차순으로 정렬한 후에 최댓값과 최솟값을 더해서 무게제한값을 넘기면 최댓값만 보트에 탈 수 있으니 구명보트를 하나 추가하고, 만약 무게제한값 이내에 있으면 2명이 탈 수 있으므로, 구명보트도 하나 추가, 최솟값도 그 다음 인덱스로 바꿔준다.

그래서 이 최댓값 인덱스가 최솟값 인덱스보다 작아질때까지 반복해주면 그리디 알고리즘으로 풀어진다.

---

#include <algorithm>
#include <vector>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(),people.end()); // 정렬
    int flag = 0; // 최솟값 체크
    for(int i=people.size()-1;flag <=i;i--){
       if(people[i]+people[flag]<=limit){
           flag++;
       }
        answer++;
    }
    return answer;
}