(프로그래머스 코딩테스트 고득점 kit) Greedy Algorithm Level3 저울

문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 합니다. 이 저울의 양팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같습니다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있습니다.

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

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

제한 사항

저울추의 개수는 1개 이상 10,000개 이하입니다.

각 추의 무게는 1 이상 1,000,000 이하입니다.

입출력 예

weight	return
[3, 1, 6, 2, 7, 30, 1]	21

문제 이해

일단 작은 숫자부터 하나씩 확인해보면서 못만드는 친구를 찾는다.

큰 추부터 넣어야 말이 되지 않을까..!? (증명은 안했다..)

왜냐하면 만약 작은 추부터 채우면 큰 추가 들어갈 자리가 없어서 못만든다고 생각할 수도 있기 때문이다.

일단 해보자.

방법은

추를 큰 값 순으로 솔팅하고
1부터 하나씩 만들수 있는지보자.
전체에서 무거운 추부터 하나씩 빼다가 결국 0이 되면 pass, 0을 못만들면 return!

코드(점수: 70점, 효율성: 꽝)

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

using namespace std;

int solution(vector<int> weight) {
    int answer = 0;
    sort(weight.begin(), weight.end(), greater<int>());
    for(int i = 1; ; i++){
        int num = i;
        for(int j = 0; j < weight.size(); j++){
            if(num == weight[j]){
                num -= weight[j];
                break;
            } 
            else if(num > weight[j]) num -= weight[j];
        }
        if(num != 0) return i;
    }
    return answer;
}

효율성을 어떻게…

엄청 고민하다가 뭐 별의별 방법을 다 고민해봤다.

이렇게 하면 될까 저렇게 하면 될까 하면서 윤호형이랑 밤마다 이야기했다.

일단 비효율의 원인은 찾았는데, 큰 추부터 확인하다보니 1부터 시작하면서 큰추부터 일일이 다 넣는건 엄청 비효율적이라는 생각이 든다.

만약 작은 추부터 보면서 그 결과값을 저장해놓을 수 있다면 그게 제일 베스트 일 것 같다.

그래서 혹시나 예제 케이스에서 생각나서 짜본 코드… 이건 나도 짜고 깜짝 놀랐다..

코드(점수: 100점)

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

using namespace std;

int solution(vector<int> weight) {
    int sum = 0;
    sort(weight.begin(), weight.end());
    for(int i = 0; i < weight.size(); i++){
        if(sum + 1 < weight[i]) return sum + 1;
        sum += weight[i];
    }
    return sum + 1;
}

방법

작은 수부터 측정한다고 했을 때 만일 i번째 추를 사용한다는 것은 i번째 추의 무게 - 1 까지는 다른 추로 표현 할 수 있다는 것을 의미한다.

예를 들어 5라는 수를 무게 5인 추로 측정하려고 한다면 5보다 작은 추들로 1,2,3,4를 표현할 수 있다는 것을 말한다.

만일 바로 이전 숫자들의 합 + 1이 weight[i]보다 작게 되면 sum + 1과 weight[i] 사이에 측정불가한 무게들이 생긴다.

그렇다면 그 중 가장 작은 원소인 sum + 1 을 return 해주면 된다.

느낀점

내가 생각을 달리하는 것 만으로 효율의 발전이 말도 안되게 증가하는 것을 볼 수 있었다.

이 방법을 내가 수학적으로 표현해낼 수 있으면 너무 좋을 것 같다.

Greedy는 내 방법에 대한 증명이 무엇보다 중요하다고 생각한다.

증명을 어떻게 할 수 있을지 공부해봐야겠다.