[백준] 2629번: 양팔저울

💻 문제 - G3

👉 제출 코드

n = int(input()) # 추의 개수
weight = list(map(int, input().split()))

dp = [[0] * (30*500+1) for _ in range(n+1)]
def solve(i, w):
    if i > n or dp[i][w]:
        return
    dp[i][w] = 1
    solve(i+1, w)
    solve(i+1, w + weight[i-1])
    solve(i+1, abs(w - weight[i-1]))
    
solve(0, 0)

n_marbles = int(input()) # 구슬의 개수
marbles = list(map(int, input().split())) # 구슬의 무게들
for m in marbles:
    if m > 30*500:
        print('N', end=' ')
        continue
    if dp[n][m] == 1:
        print('Y', end=' ')
    else:
        print('N', end=' ')

추를 모두 거쳐서 구슬의 무게를 만드는 방법은 3가지이다.

• 추를 어디에도 올리지 않는다.
• 추를 저울에 올린다.
• 추를 구슬 쪽 저울에 올린다.

P(i, w)를 i번째 추까지 사용해서 구슬 무게 w를 만들 수 있는지의 여부라고 했을 때,

• P(i+1, w)
• P(i+1, w + weight[i])
• P(i+1, abs(w-weight[i])

위와 같은 재귀를 만들 수 있다.
재귀를 3번 호출하는 것은 성능이 안 좋지만, 추의 최대 개수는 30개로 크지 않고, dp를 2차원 배열로 만들어 이전 값들을 저장한다.

시간 초과를 방지하기 위해, i가 추의 개수보다 많거나 이미 i번째 추를 사용하여 w를 만든 경우 리턴한다.

런타임 에러가 발생했는데 문제 조건에 따라 다음과 같은 코드를 추가하여 해결했다.

if m > 30*500:
    print('N', end=' ')
    continue

문제에서 추의 무게는 500g 이하이고 추의 개수는 30 이하라고 하는데 확인하고자하는 구슬의 무게는 40,000보다 작거나 같은 자연수라고 한다.

주어진 추 무게의 총합은 500g * 30개 = 15,000으로 40,000보다 작지만 15,000보다 큰 수가 들어왔을 때 N을 출력할 수 있어야 한다.