[백준] 2437 파이썬

문제

---

• 백준 2437 (골드 2)

백준 2437

무게가 양의 정수인 n개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최소값을 구하는 문제였다.
같은 무게의 추가 여러 번 주어지는 경우도 있었다.
무엇보다 문제의 조건이 깔끔해서 좋았다.

내 코드

---

문제는 정말 깔끔해서 쉽게 풀릴 것 같았지만 생각보다 무슨 알고리즘을 써야할지 감이 잡히지 않았다.
그래서 우선은 combinations을 활용해서 모든 경우의 수를 고려하는 방식으로 코드를 작성하였다.
1%도 넘기지 못하고 시간초과가 발생하였다.

틀린 코드

import sys
from itertools import combinations
input = sys.stdin.readline

n = int(input())
scales = list(map(int, input().split()))

def check(target):
    for j in range(n + 1):
        for subset in combinations(scales, j):
            if sum(subset) == target:
                return True
    return False

for i in range(1, sum(scales) + 2):
    if not check(i):
        print(i)
        exit()

다음으로는 dp를 활용하여서 코드를 작성해보려고 하였지만 실패하였다.
그래서 이리저리 질문글들을 찾아 보다가 아래와 같은 글을 보게 되었다.

예를 들어보자.
만약 [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는 현재까지의 모든 무게추의 합이된다.

위와 같은 아이디어를 코드에 풀어내니 코드도 정말 깔끔하게 나왔고 바로 통과할 수 있었다.

정답 코드

import sys
input = sys.stdin.readline

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

ans = 1

for scale in scales:
    if ans < scale:
        break
    ans += scale

print(ans)

이런 문제를 해결하기 위한 아이디어를 금방 떠올리는 방법은 뭐가 있을까?
역시 많은 문제를 푸는 것밖에 없다는 생각이 들었다.