백준 2629 : 양팔저울[파이썬]

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

2629번: 양팔저울

1. 문제 설명

양팔 저울을 이용해 주어진 추로 특정 무게를 만드는 문제이다.

추를 사횽해 무게를 만드는 방법은 3가지 이다.

1. 추의 무게를 더한다.
2. 추의 무게를 뺀다.
3. 추를 사용하지 않는다.

위 3가지 규칙으로 만들 수 있는 모든 무게를 dp에 저장한다.

재귀를 사용해서 코드를 작성했다.

 

2. 코드 설명

n = int(input())
weight = list(map(int, input().split()))
m = int(input())
glass = list(map(int, input().split()))

dp = [[0 for j in range((i+1)*500+1)] for i in range(n+1)]

def cal(num, w):
    if num > n:
        return
    if dp[num][w]:
        return

    dp[num][w] = 1

    cal(num+1, w)
    cal(num+1, w+weight[num-1])
    cal(num+1, abs(w-weight[num-1]))

cal(0, 0)

for i in glass:
    if i > 15000:
        print('N', end=' ')
    elif dp[n][i] == 1:
        print('Y', end=' ')
    else:
        print('N', end=' ')

추의 개수가 많아질수록 한 번에 재귀를 3번 호출하는 것은 성능 문제를 초래할 수 있다.

따라서 dp를 2차원 배열로 만들어 추의 개수별로 만들 수 있는 무게 리스트를 만든다.

이미 같은 추의 개수로 똑같은 무게를 만들었다면,

다음 과정을 같으므로 함수를 return하면 된다.