[백준] 2629 - 양팔저울

양팔저울

생각 흐름

1. 문제 설명부터 냅색 알고리즘이라고 되어 있다.
2. 아마 없다면 못 풀지 않았을까? 냅색 알고리즘도 안 본 지 오래 되어서 다시 찾아볼 정도였다.
3. 냅색 알고리즘은 일단 i번째 가방에 대해서 포함 여부를 분기로 나누는 것이다.
   나누면서 i-1번째까지 다뤘을 때 i번째 물건의 무게보다 적은 무게를 담았을 때의 가치 + i번째 물건의 가치와 현재 무게에서 아무 것도 안 담을 때의 가치 중 최대값을 저장한다.
4. 이 알고리즘을 이 문제에 적용한다면,
   1. 점점 i번째 추를 고려사항에 포함시킨다.
   2. 구슬의 무게 j에 대해서 아무 것도 안 했을 때, 왼쪽에 놓았을 때, 오른쪽에 놓았을 때를 모두 OR로 묶는다.
5. 이때의 문제는, 예제 1에서 추가 1, 4로 주어지면 오른쪽에 4를 올리고 왼쪽에 1을 올릴 수가 없다는 것이다. 즉 무게가 3인 구슬의 무게를 정확히 잴 수 없다고 나온다.
6. 왜냐하면 일단 무게 3 짜리는 $i=1$에선 절대 안 되고, $i=2$에서 그 가능 여부가 구해질 수 있는데 $3 - 4 = -1, \ 3 + 4 = 7$이어서 $i=2$에서도 구할 수가 없기 때문이다.
7. 이것 때문에 막혀서 검색을 해봤는데, abs를 쓰는 코드를 보고 무릎을 탁 쳤다.
8. 내 알고리즘에서 j - weight[i]는 오른쪽에 놓는 경우, j + weight[i]는 왼쪽에 놓는 경우를 말한다. (오른쪽에 놓는다는 것은 추를 더한다는 것이므로, 더하기 전 무게의 가능 여부를 알아야 하고, 왼쪽에 놓는다는 것은 추를 뺀다는 것으로, 빼기 전 무게의 가능 여부를 알아야 한다.)
9. 이때 내가 j - weight[i]가 음수일 경우엔 무조건 불가능이도록 예외 처리를 했는데, 이를 abs(j - weight[i])로 바꾸면, 왼쪽과 오른쪽의 추를 바꾼다는 뜻이다.
10. 예를 들어 문제가 되는 $3 - 4 = -1$에서 보면, 오른쪽에 $-1$짜리 추가 있는 상태에서 다시 $4$짜리 추를 올려놓는다는 뜻인데 오른쪽에 $-1$짜리 추라는 것은 왼쪽에 $1$짜리 추가 있었다는 뜻이 된다.
11. 만약 오른쪽에 $1$짜리 추가 있었다면 이를 그대로 왼쪽으로 옮길 수도 있다. 바로 이 과정이 abs를 취해주는 이유이다.
12. 음수가 된다면 그 음수에 절대값을 취해줘서 오른쪽에 그만큼의 추가 있던 적이 있는지를 구하고, 만약 그렇다면 이는 그대로 왼쪽으로 옮겨질 수 있다. 즉 왼쪽에 그만큼의 추가 있을 수 있는지를 구하기 위해 음수에 절대값을 취해준다.

풀이

2차원 dp를 사용한다.
dp\[j\]\[i\]는 i번째까지의 추를 이용해서 무게 j를 잴 수 있는지 여부이다.

최상단에서 i를 n_weight까지 돌리면서 추를 포함시킨다.
그 안에서 1부터 40000까지 각 구슬 무게를 잴 수 있는지에 대한 여부를 구한다.
dont는 그 추로 아무 것도 하지 않을 때이다. 아무
left는 weights[i]를 왼쪽에 놓을 때이다. j + weights[i]의 값을 가져온다.
right는 weights[i]를 오른쪽에 놓을 때이다. j - weights[i]의 값을 가져온다.
단, j - weights[i]가 음수라면 절대값을 취해준다. 이는 이전에 오른쪽에 abs(j - weights[i])만큼의 무게를 잰 적이 있는지를 의미한다. 있다면, 그만큼의 추를 왼쪽으로 옮겨 마이너스의 무게를 만들고, 이것에 현재 오른쪽에 추가하려는 weights[i]를 합한 무게를 잴 수 있다는 뜻이다.

코드

import sys


scan = sys.stdin.readline


def solution():
    n_weight, weights = get_input()
    n_bead, beads = get_input()
    dp = [[0 for _ in range(n_weight + 1)] for _ in range(40001)]

    for i in range(1, n_weight + 1):
        dp[weights[i]][i] = True
        for j in range(1, 40001):
            dont = dp[j][i - 1]
            left = dp[j + weights[i]][i - 1] if j + weights[i] <= 40000 else 0
            right = dp[abs(j - weights[i])][i - 1] if abs(j - weights[i]) <= 40000 else 0
            dp[j][i] = dp[j][i] | dont | right | left

    for i in range(1, n_bead + 1):
        sys.stdout.write("%s " % ('Y' if dp[beads[i]][n_weight] else 'N'))


def get_input():
    n = int(scan())
    arr = [0] + list(map(int, scan().split()))
    return n, arr


solution()