프로그래머스 : 구명보트

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

코딩테스트 연습 - 구명보트 | 프로그래머스

1. 정렬한다.

2. 제일작은놈과 큰놈을 보트에 태우는데 태울수없다면 큰놈은 혼자타야한다.

3. 큰놈이 혼자탈경우 제일작으놈과 그다음 큰놈으로 태운다. 이걸 반복

4. 보트에 이미 탄놈은 flag로 구분

 

오름차순 풀이)

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

using namespace std;

int solution(vector<int> people, int limit) {
    int cnt = 0;
    int vote = 0;
    int n = 0;
    vector<bool> flag(people.size(),0);

    sort(people.begin(),people.end());
    for(int i=people.size()-1; i>=0; i--)
    {
        if(!flag[i] && !flag[n]){
            if(people[n]+people[i] <= limit)
            {
                flag[i] = 1;
                flag[n] = 1;
                n++;
                cnt++;
            }
            else{
                flag[i] = 1;
                cnt++;
            }
        }
    }
    return cnt;
}

 

내림차순 풀이)

sort후 reverse해서 내림차순 할수 있는것 알아두자

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

using namespace std;

int solution(vector<int> people, int limit) {
    sort(people.begin(), people.end());
    reverse(people.begin(), people.end());
    int N = (int)people.size();
    int res = 0;
    for (int i = 0, j = N - 1; i <= j; i++) {
        if (people[i] + people[j] <= limit) {
            j--;
        }
        res++;
    }
    return res;
}

 

 

# sort하고 앞에서만 비교했었음 앞뒤로 비교하면서 큰놈들을 빼야함