[프로그래머스]탐욕법(Greedy) : 구명보트(level 2) (c++)

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

프로그래머스

 

 

참고한 블로그 : https://moonsupport.tistory.com/240

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
   
    // 오름차순 정렬
    sort(people.begin(), people.end());
   
    // 가장 작은 값과 가장 큰 값부터 계산
    int low = 0;
    int high = people.size() - 1;
    int cnt = 0;

    // low와 high가 엇갈리면 종료
    while (low <= high)
    {
        // 작은 값 + 큰 값이 limit 이하이면 작은값도 out
        if (people[low] + people[high] <= limit)
        {
            low++;
        }

        // 큰 값부터 out
        high--;
        cnt++;
    }

    return cnt;
}

 

 

이번에도 혼자 푸는것에 실패한 그리디 ㅜㅜ

위에 링크한 블로그를 보니 아...퀵소트st다.

 

저 위에 while문 내부는 아래코드를 좀더 간략하게 한것이다.

// low와 high가 엇갈리면 종료
while (low <= high)
{
    // 작은 값 + 큰 값이 limit 이하이면 작은값도 out
    if (people[low] + people[high] <= limit)
    {
        low++;
        high--;
        cnt++;
    }
    // 작은 값 + 큰 값이 limit을 넘으면 큰값만 out
    else
    {
        high--;
        cnt++;
    }
}

 

vector를 정렬하여,

양 끝에서부터 좁혀온다고 생각하면 되겠다.