[Lv3] 저울

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

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

저울추가 담긴 배열 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

 

입출력 예 설명

문제에 나온 예와 같습니다.

 

 

문제 원출처: https://www.digitalculture.or.kr/koi/selectOlymPiadDissentList.do

---

 

n개의 수가 든 배열에서 1~n개의 숫자의 조합(나열이든 사칙연산이든)으로 만들 수 있는 수들을 구하는 방법은 이미 다뤘습니다.

[Coding Quiz/programmers] - [Lv2] 소수 만들기

 

하지만 이 문제에서는 이 방식으로 수를 만들면 Overflow가 발생해서 수가 틀어지게 되어있습니다.

(수 자체를 구하면서 빈 공간을 찾으려보면 Overflow지만, 구해지지 않는 최소의 숫자 상에서는 Overflow가 발생하지 않을 정도의 아슬아슬함.)

 

프로그래밍 관점이 아니라 수학적으로 풀어야 하는 문제입니다. 이러면 프로그래밍 기법과 상관없이 수학문제가 되지 않나.. 반복된 상황에서 수학적인 공식을 찾는 것도 능력이라면 능력이니.. 여튼...

 

 

배열 0 [3, 1, 6, 2, 7, 30, 1]가 주어진다면, 이 배열을 오름차순으로 정렬합니다. (앞에 가상의 0이 있다고 생각합니다.)

 

00 [01, 01, 02, 03, 06, 07, 30]이 되겠죠.

만들 수 있는 최소 숫자는 가장 앞의 1이 됩니다. 당연한 소리지만 4로 시작한다면 가장 작은 수가 4이니 우선 그 미만은 만들 수 없는 수입니다. 가장 앞이 1이 아니라면 빠르게 답이 나옵니다.(1)

 

1부터 시작한다면, 순서대로 누적해봅니다.

00 [01, 02, 04, 07, 13, 20, 50]이 됩니다.

 

원래 배열과 누적합 배열을 다음과 같이 비교할겁니다.

00 [01, 01, 02, 03, 06, 07, 30],

00 [01, 02, 04, 07, 13, 20, 50]

 

동일 i 기준, 누적합[i]+1가 원배열[i+1] 이상이어야 하며, 미만이되면 그 때의 누적합[i]+1부터 만들 수 없는 수입니다.

모두 비교하고도 통과 되었다면, 마지막 수인 50+1=51이 만들 수 없는 수입니다.(모든 수들의 합+1)

 

맨 처음이 1이 아니면 바로 1이 만들 수 없는 최소의 수가 되는 것도 0을 통해 배열 자체로 확인할 수 있습니다.

 

---

이 공식을 유지하면서 모든 수를 만들 수 있는 배열(중복없이)은 어떻게 생겨먹었을까요.

직접 연관이 있는건 아니지만, 이번 상황을 보고나면 이해가 더 빨라집니다.

00 [01, 02, 04, 08, 16, 32]

00 [01, 03, 07, 15, 31, 63]

 

2의 배수씩. 즉 이진법을 생각하면 됩니다. 이진법은 모두 2^n의 합들로 모든 수를 표현 가능하죠.

그리고 01111+00001 = 10000이 되듯,

4자리의 1이 가득찬 수(4가지 수 1,2,4,8의 합인 15)에 1만 더하면 다음 수인 16이 되죠.

---

 

00 [01, 01, 02, 03, 06, 07, 30],

00 [01, 02, 04, 07, 13, 20, 50]로 돌아와서 봅시다.

 

13 입장에서는 이미 1~13까지는 어떻게든 만들 수 있는 수입니다.

14부터는 새로운 재료가 필요하죠. 13에게 필요한건 1~14의 수입니다.(오름차순 정렬상 6이상의 수가 들어오지만)

14면 그 자체로 완성본이고, 1~13은 이미 만들 수 있는 13~1에 더하기만 해도 되니까요.

1~13 중 7이 들어와줬네요.

14도 만들 수 있을 뿐더러 이미 1~13을 자체적으로 만들 수 있으니,

1+7

2+7

3+7

...

12+7

13+7

으로 1~20까지 바리에이션이 늘어났습니다.

 

이제 20 입장에서는 이미 1~20까지는 어떻게든 만들 수 있는 수입니다.

21부터는 새로운 재료가 필요하죠. 20에게 필요한건 1~21의 수입니다.(오름차순 정렬상 7이상의 수가 들어오지만)

21이면 그 자체로 완성본이고, 1~20은 이미 만들 수 있는 20~1에 더하기만 해도 되니까요.

그런데 아득히 먼 30이 들어왔네요.

1~20//30,31~50의 바리에이션이 되겠어요. 근데 오름차순 정렬이라 배열을 뒤에 아무리 뒤져도 더 큰 수 뿐이죠.

21~29는 만들 수 없는 수가 됐습니다.

 

 

코드는 간단하지만, 간단해서 까먹기 쉽습니다.(1을 더했던가.. 앞으로 비교했던가 뒤로 비교했던가 하면서)

 

수학적으로 한번 제대로 보고나면 잘 안까먹을 것 같아서 글이 길었습니다.

 

public int solution(int[] weight) {
    Arrays.sort(weight);
    if(weight[0]!=1) return 1;
    int[] sum = new int[weight.length];
    int tmpsum = 0;
    for(int i=0;i<weight.length;i++) {
        tmpsum+=weight[i];
        sum[i]=tmpsum;
        if(i<weight.length-1 && sum[i]+1<weight[i+1]) {
            return sum[i]+1;
        }
    }
    return sum[sum.length-1]+1;
}