[백준] 2437번 저울 - 파이썬(Python)

문제 (링크)

https://www.acmicpc.net/problem/2437

2437번: 저울

 

나의 풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

target = 1

for num in arr:
    if target < num:
        break

    target += num

print(target)

 

코드 설명 및 풀이법

처음엔 1원부터 모든 무게의 합까지 확인하면서 연속된 합이 끊어지는 부분을 구해야겠다고 생각했다.

 

이를 위해서 무언가 누적합이나 DP를 이용해야할 것 같은데 도저히 방법이 떠오르지 않았다.

 

결국 풀이를 봤는데, 바로 이해가 되질 않아서 여러 해설을 찾아다녔고, 정말 명쾌한 풀이를 발견했다.

 

https://aerocode.net/392

백준 2437 풀이 및 해설

 

풀이의 핵심은 다음과 같다.

 

편의상 미지수를 사용하겠지만 결코 어렵지 않으니 잘 따라가보자.

 

총 N개의 저울추 중에서 몇 가지를 뽑아서 지금까지 K만큼의 무게를 측정할 수 있다고 가정할 때,

 

무게가 X인 새로운 저울추가 추가된다고 하면, 새로 측정할 수 있는 무게는 (1 ~ K) * X가 된다.

 

 

예를 들어보자.

 

만약 [1, 1, 2]의 무게추가 있고 이 세 가지의 무게추를 이용해 측정할 수 있는 무게는 1, 2, 3, 4이다.

 

즉, K = 4인 것이다.

 

여기서 무게가 3인 새로운 저울추가 추가된다고 가정해보자.

 

무게가 3인 저울추가 추가된다면, 새로 측정할 수 있는 무게는 기존에 측정할 수 있던 무게 (1 ~ K) + 새로운 무게추가 되므로

 

1 + 3 = 4

2 + 3 = 5

3 + 3 = 6

4 + 3 = 7

 

으로 각각 4, 5, 6, 7이 된다.

 

여기서 4는 이미 [1, 1, 2]의 무게추만으로 만들 수 있기 때문에 제외하면,

 

무게가 3인 새로운 저울추가 새로 추가되면 이제 1 ~ 7까지의 무게를 측정할 수 있게 되는 것이다.

 

그리고 이 단계를 거칠 때마다 K는 현재까지의 모든 무게추의 합이된다.

 

 

그렇다면 새로운 무게가 추가될 때 1 ~ K중 측정할 수 없는 무게는 어떻게 판단할까?

 

이번엔 기존 [1, 1, 2]에 무게가 5인 무게추를 추가한다고 가정해보자.

 

기존 무게추로 측정할 수 있는 무게 역시 1, 2, 3, 4이다.

 

이제 무게가 5인 무게추를 새로 추가해보자.

 

동일한 로직으로, 무게가 5인 무게추가 추가된다면 새로 측정할 수 있는 무게는

 

1 + 5 = 6

2 + 5 = 7

3 + 5 = 8

4 + 5 = 9

 

으로 각각 6, 7, 8, 9가 된다.

 

이로써 무게가 5인 무게추가 새로 추가되면 [1, 1, 2, 5]의 무게추로 측정할 수 있는 무게는

 

1, 2, 3, 4, 6, 7, 8, 9가 되고 이 중 측정할 수 없는 무게의 최소값은 5가 된다.

 

 

이를 일반화하는 규칙은 다음과 같다.

 

앞서 언급했듯, 총 N개의 무게추 중 몇 가지를 뽑아 1 ~ K만큼의 무게를 측정할 수 있다고 가정할 때,

 

K는 현재까지 사용한 모든 무게추의 합과 같다. (모든 무게추를 사용했을 때 측정할 수 있는 값이므로)

 

그리고 무게가 X인 새로운 무게추를 추가한다고 했을 때, 측정할 수 없는 무게가 생기는 경우는

 

기존 측정할 수 있던 1 ~ K와, 새로 측정할 수 있는 무게인 (1 ~ K) * X 사이에 빈 공간이 생길 때가 된다.

 

이 공간이 발생하는지에 대한 여부는 새로운 무게추 X와 기존 측정할 수 있는 무게의 최대값인 K를 비교해 구할 수 있다.

 

지금까지 1 ~ K까지의 무게를 측정할 수 있었으므로, 다음에 측정해야 할 무게는 K+1이 될 것이다.

 

하지만 만약 새로운 무게추의 무게 X가 이 K + 1보다 크게 되면 결국 K + 1은 측정할 수 없는 수가 된다.

 

이 원리를 이용하여 코드를 짜면 정답을 받을 수 있다.