[python] 백준 2437번 : 저울

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

2437번: 저울

 

1. 구현 

n = int(input())
weights = list(map(int, input().split()))
weights.sort()
check = 0
for w in weights:
    if check + 1 >= w:
        check += w
    else:
        break

print(check+1)

 

2. 틀린 코드 

n = int(input())
weights = list(map(int, input().split()))
dp = [0]*(sum(weights)+1)


# dfs : 합쳐야하는 타겟 넘버의 개수가 2개일 때만 확인하기
# 일반화하기) 타겟 넘버의 개수가 2, .... n 일때
def dfs(count, arr, target):
    global dp

    if count == target:
        dp[sum(arr)] = 1
        return
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            arr.append(weights[i])
            dfs(count+1, arr, target)
            visited[i] = False
            arr.pop()

for i in range(1, n+1):
    visited = [False] * n
    dfs(0, [], i)

for i in range(1, sum(weights)+1):
    if dp[i] == 0:
        print(i)
        break

구글링해봤더니 dfs로 저울 문제를 풀길래 백트래킹을 이용하면 풀 수 있지 않을까 싶어 dfs로 구현했다. 알고보니 번호가 문제명이 같은 다른 문제였고 이 문제는 dfs를 이용하면 시간 초과가 발생한다. 

반례 )  

19
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144