[프로그래머스]탐욕법(Greedy) : 저울 (level 3)(c++)

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

코딩테스트 연습 - 저울

 

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

using namespace std;

int solution(vector<int> weight) {

    // 오름차순 정렬
    sort(weight.begin(), weight.end());
   
    int sum = 0;
    for (int w : weight)
    {
        /*
            S[i] = a[0] + ... + a[i] 라 할때,
            S[i] + 1 < a[i + 1] 이라면
            S[i] + 1 은 만들 수 없다.
        */
        if (sum + 1 < w)
        {
            break;
        }
        sum += w;
    }

    return sum + 1;
}

 

 

저울추가 담긴 배열 weight가 매개변수로 주어질 때,
이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 return 하도록 solution 함수를 작성해주세요.

예를 들어, 무게가 각각 [3, 1, 6, 2, 7, 30, 1]인 7개의 저울추를 주어졌을 때,
이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21입니다.

 

측정할 수 없는 무게 중 최솟값을 구해야 하므로 

weight배열을 오름차순 하는 것으로 생각을 시작해야 한다. 

 

 

그리고 절대 수를 만들 수 없는 경우의 예시를 한번 생각해보자.

이를테면 입력값으로 [1, 5]가 주어진다면, 절대 2는 만들 수 없다.

 

한 번 더 생각해보자

[1, 2, 5]가 주어진다면, 4는 만들 수 없다. 

왜냐면 두번째까지의 숫자를 모두 더해봤자 3인데, 

그 뒤에 주어지는 숫자는 4를 뛰어넘고 5이기 때문이다.

 

 

마찬가지로 문제에서 주어진 예시 [1, 1, 2, 3, 6, 7, 30] 또한

6번째 수까지 모두 더해봤자 20이고, 그 뒤의 숫자는 바로 30이기 때문에

21은 만들수가 없다. 

 

이걸 수식의 힘을 좀 빌려서 표현하면 다음과 같다.

for (int w : weight)
{
    /*
        S[i] = a[0] + ... + a[i] 라 할때,
        S[i] + 1 < a[i + 1] 이라면
        S[i] + 1 은 만들 수 없다.
    */
    if (sum + 1 < w)
    {
        break;
    }
    sum += w;
}

 

 

 

번외)

예시 [1, 1, 2, 3, 6, 7, 30] 이 19를 만들 수 있을 거란걸

해보지도 않고 저런 수식으로 어떻게 알지?? 라는 의구심이 든다면...

 

입력이 [1, 2, 4, 8, 16 ... ] 이렇게 2의 제곱수로 주어지는 경우를 생각해보자

우리는 저 숫자들의 조합으로 13을 만들 수 있을 거란걸 안다 :)