BOJ 2437 저울

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

2437번: 저울

 

naive한 접근 완탐이었다. combination을 이용하여 target 숫자를 만들 수 있는지 확인하여 만들 수 없으면 그 수를 출력하는 것이다.

from itertools import combinations
n = int(input())
c = list(map(int, input().split()))
c.sort()
answer = 1

def solve(target):
    for i in range(len(c)):
        for comb in combinations(c, i):
            if sum(comb) == target:
                return True
    return False

while True:
    if not solve(answer):
        print(answer)
        break
    answer += 1

 

(당연히 TLE를 받았다)

굳이 모든 경우를 다 봐야할까? 라는 생각이 들었다.
그러면서 가정을 하나 해봤다.
"현재까지 사용한 숫자들로 0 ~ e까지 만들 수 있다면, 추가로 숫자 k를 더 사용하면 0 ~ k + e 까지 만들 수 있을까?"
이를 가능하게 하는 조건은 e + 1 >= k 일때 밖에 없다.

구간 [0,e] 에서 숫자 k를 더하면 [k, k+e]가 된다.
이때, e + 1 >= k 라면 구간 [0,e] 와 구간 [k,k+e] 는 겹치게된다.

만들 수 없는 가장 작은 숫자를 구해야 하므로, 주어진 숫자들 중 작은 숫자들 부터 추가가 가능한지 아닌지 확인해보면 된다.

정답 코드는 다음과 같다.

n = int(input())
c = list(map(int, input().split()))
c.sort()
e = 0
for a in c:
    if e + 1 < a: break
    e += a
print(e+1)