백준 2629 [python]

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

N = int(input())
beads = list(map(int, input().split()))
s = set()
for bead in beads:
    temp_set = set()
    for val in s:
        temp_set.add(bead + val)
        temp_set.add(abs(bead - val))
    temp_set.add(bead)
    s |= temp_set

t = int(input())
t_list = list(map(int, input().split()))
for ts in t_list:
    print("Y" if ts in s else "N", end = ' ')
print()

처음 푼 코드는 dp를 이용하지 않고 set을 이용해서 풀었다. 코드가 돌아가는 과정을 생각하면 dp를 이용한 dfs와 유사하다고 생각한다.

다른 방법으로 문제를 풀 수 있다고 해서 다른 풀이를 시도해봤다.

N = int(input())
beads = list(map(int, input().split())) + [0]
dp = [[False, -1] for i in range(40001)]

def find_dp(idx, v):
    if idx == N: return
    if dp[v][0] and dp[v][1] >= idx : return
    dp[v] = [True, idx]
    
    find_dp(idx + 1, v + beads[idx + 1])
    find_dp(idx + 1, abs(v - beads[idx + 1]))
    find_dp(idx + 1, v)
    
find_dp(0, beads[0])
find_dp(0, 0)

T = int(input())
t_list = list(map(int, input().split()))
for t in t_list:
    print("Y" if dp[t][0] else "N", end = ' ')
print()

dp를 일차원 배열로 놓고 문제를 해결하려 했다. 문제는 경우의 수 가지치기가 제대로 안된다는 것이다. 구슬이 4, 8, 27일 때, i = 1일 때 4를 더한 4와 i = 2일 때 8 - 4로 계산된 4를 비교해보자. 두 번째 4는 가지치기 하면 된다. 그런데 i = 2일 때 4를 넣고 8을 넣지 않은 경우인 4는 가지치기 하면 안된다. 왜냐하면 i = 1일 때 4인 놈이 넘어온 것이기 때문에 i = 3까지 경우의 수를 고려해야 하기 때문이다. 이걸 해결하기 힘들어서 구글링했다.

N = int(input())
beads = list(map(int, input().split())) + [0]
dp = [[False for i in range(40001)] for i in range(N)]

def dfs(idx, val):
    if idx == N or dp[idx][val]: return
    dp[idx][val] = True
    
    dfs(idx + 1, val)
    dfs(idx + 1, val + beads[idx + 1])
    dfs(idx + 1, abs(val - beads[idx + 1]))

dfs(0, 0)
dfs(0, beads[0])

T = int(input())
t_list = list(map(int, input().split()))
for t in t_list:
    print("Y" if dp[N - 1][t] else "N", end = ' ')
print()

dp[i][j]에 추가 i개(0부터 i - 1) 있을 때 j라는 무게를 만들수 있는지 여부를 담는다. dp[i]는 재귀함수에서 dp[i - 1]에서 계산된 값을 근거로 계산된다. 경우의 수는 dp[i]중에 j라는 무게를 만든 경우가 여러개 존재할 때, 하나만 살리고 나머지는 폐기하는 방식으로 가지치기한다. 그러니까 i번째 추까지 만들 수 있는 추의 무게를 계산했을 때, 만들어진 무게가 겹칠 경우 그것만 가지치기한다는 이야기다. i가 다르고 j가 같은 경우는 아무 연관이 없는 것이므로 가지치기 하지 않는다. 이걸 가지치기 해버리면 그 뒤에 가능한 경우의 수가 짤리게 된다. 결국 맨 위의 코드와 비슷한데 dfs로 진행되는 것만 다르다.

i가 몇번째이든 상관 없이 같은 무게가 나오면 가지치기 해야한다고 착각했고, 거기서 헤어나오기가 힘들어 풀기 어려웠다. 반례를 신경써서 떠올리고 조금 더 신중하게 생각하며 문제를 풀어야겠다.