[백준] 2629 - 양팔저울 (G3)

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

2629번: 양팔저울

추의 개수와 각 추의 무게가 주어졌을 때, 주어진 추들을 양팔 저울에 올려 측정할 수 있는 무게의 종류를 구하는 문제이다.

추를 양팔 저울의 한 쪽에만 올리는 경우와 다른 반대쪽에도 올릴 수 있는 경우가 있다는 점이 이 문제의 어려운 점이다.

 

측정하려는 무게를 x, 현재 사용하는 추의 무게를 w, 이전까지  측정한 적 있던 무게를 p 라고 하자.

 

그렇다면 측정하려는 무게를 양팔저울의 왼쪽에 놓았을 때 나머지 추를 왼쪽과 오른쪽에 적절히 놓아 등식을 만들 수 있으면 된다. 이때 추를 적절히 놓는 방식은 아래와 같이 3가지 경우의 수가 나온다.

 

1. x = w + p

2. x + p = w

3. x + w = p

 

이전에 아무런 추를 놓지 않고 현재 놓는 추가 처음 놓는 추인 경우가 있을 수도 있지 않냐고 생각할 수 있다.

이 경우에는 p = 0 인 경우로 생각한다.

측정하려는 무게와 이전에 측정했던 무게에 대한 추, 새로운 추를 모두 왼쪽에 놓는 경우는 불가능하다.

 

이제부터 이전에 측정한 적 있는 무게들을 모두 저장해가며 현재 측정하려는 무게 x 를 측정할 수 있는지 체크해보자.

위의 세 식을 x 에 대해 정리하면 아래와 같이 정리된다.

 

1. x = w + p

2. x = w - p

3. x = p - w

 

그런데 측정하는 무게 x 는 절대 음수가 될 수 없다.

따라서 위 식은 아래와 같이 정리할 수 있다.

 

1. x = w + p

2. x  = abs(w - p)

 

이제 이를 이용하면 dp 점화식을 세울 수 있게 된다.

 

무게가 w인 i 번째 추까지 중에서, x 라는 무게를 만들 수 있다는 것은

i-1 번째 추까지 사용하였을 때 p 라는 무게를 만든 적이 있었을 때,

w+p 로 만들 수 있거나, abs(w-p) 로 만들 수 있다.

 

dp[i][x] = dp[i-1][w+p]   ||   dp[i-1][ abs(w-p) ]

 

그리고 간과하면 안되는 것은 바로 직전추까지 측정 가능했던 모든 무게를 저장해야 하기 때문에

x = p 인 경우, 즉 현재 추를 사용하지 않는 경우도 포함이 되어야 한다는 것이다.

이것까지 고려해주면 dp 식은 아래와 같이 나온다.

 

dp[i][x] = dp[i-1][w+p]   ||   dp[i-1][ abs(w-p) ]   ||   dp[i-1][p]

 

이를 코드로 구현하면 아래와 같다.

n = int(input())
weights = list(map(int, input().split()))
dp = [[0 for _ in range(40001)] for _ in range(n+1)]
dp[0][0] = 1
for marble in range(1, n+1):
    weight = weights[marble-1]
    for check_weight in range(40001):
        if dp[marble-1][abs(check_weight-weight)]:
            dp[marble][check_weight] = 1
        if check_weight+weight <= 40000 and dp[marble-1][check_weight+weight]:
            dp[marble][check_weight] = 1
        if dp[marble-1][check_weight]:
            dp[marble][check_weight] = 1

q = int(input())
queries = list(map(int, input().split()))
ans = []
for query in queries:
    if dp[-1][query]:
        ans.append('Y')
    else:
        ans.append('N')
print(*ans)

주의 사항으로는

1) w+p 를 할 때, 설정한 배열의 범위가 넘어가지 않도록 주의하자.

2) 40000의 무게까지 측정 여부를 시도하므로, 40001 까지 배열을 선언해야 한다.

3) 추를 아무것도 사용하지 않았을 때는 0의 무게가 이미 측정된 것으로 가정한다.

(위 코드에서 dp[0][0] = 1)

 

정도가 있을 것 같다.

사실 dp 식을 보면 알겠지만, 이 dp는 0-1 냅색 문제와 같다.

(특정 추를 사용하는 경우, 안하는 경우, 그 때의 무게들)

기본 냅색 문제와 차이점이 있다면 특정 무게를 측정할 수 있는지 없는지 결정하느냐 최대를 찾느냐 정도의 차이일 것 같다.

 

이 문제를 조금 더 어렵게 만든다면, 특정 무게를 측정할 수 있었다면, 그 무게를 측정하는데 필요한 최소 추의 개수 또는 최대 추의 개수를 구하라고 하거나, 해당되는 추의 조합을 구하라고 하면 더 어려워질 것 같다.