백준 2629번: 양팔저울 (Python)

접근

양팔 저울이 잴 수 있는 무게는 양팔에 올라간 추의 무게의 차이라는 것을 알 수 있다. 예를 들어 무게가 각각 1, 4, 9g인 추가 있다면 첫번째 1g 추를 왼쪽에 올릴 수도 있고, 오른쪽에 올릴 수도 있고, 올리지 않을 수도 있다. 그리고 두번째, 세번째 추 또한 동일하게 3가지 경우의 수를 가진다. 이 모든 경우에 대해 좌우 차이를 구하면 답을 구할 수 있을 것이다. 하지만 이렇게 풀면 당연히 시간이 초과될 것이다.

중복을 줄일 수 있는 방법은 추 무게의 좌우 차이가 중요하다는 것을 생각해보면 된다. 왼쪽이 100g이고 오른쪽이 200g이어도, 왼쪽이 450g이고 오른쪽이 550g이어도 100g의 무게를 측정하는 것은 동일하다. 그리고 그 무게를 구성하는 추의 종류가 어떻게 바뀌더라도 좌우 차이가 동일하다면 같은 무게를 측정하고 있는 것이다. 이 점을 생각하며 dp 리스트를 다음과 같이 채워 넣으면 된다.

dp[i][j] = i번째 추를 놓으려고 할때 현재의 무게차이 j

코드

import sys

n = int(sys.stdin.readline())
weight = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
check = list(map(int, sys.stdin.readline().split()))
possible = []
ans = [[0 for _ in range(15001)] for __ in range(n + 1)]


def scale(weight, n, now, left, right):
    new = abs(left - right)
    if new not in possible:
        possible.append(new)
    if now == n:
        return 0
    if ans[now][new] == 0:
        scale(weight, n, now + 1, left + weight[now], right)
        scale(weight, n, now + 1, left, right + weight[now])
        scale(weight, n, now + 1, left, right)
        ans[now][new] = 1


scale(weight, n, 0, 0, 0)
for i in check:
    if i in possible:
        print('Y', end=' ')
    else:
        print('N', end=' ')

더 생각해 볼 것?

냅색 문제라고 하여 이전에 풀었던 냅색 문제를 찾아 확인해봤지만, 그 방법이 아닌 다른 방법으로 풀게 되었다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!