양팔저울을 이용해서 무게를 알아낼 수 있는 추를 찾는 방법

2629번: 양팔저울

 

양팔저울에 1g과 4g의 추를 이용해서, 어떤 구슬이 3g인지 확인할려면 한쪽에 1g의 추, 3g의 구슬을 놓고

 

다른 한쪽에는 4g의 추를 올려놓은 다음 양쪽이 균형을 이루는지 확인하면 된다

 

가지고 있는 추와 무게를 확인하려는 구슬이 주어질때 무게를 확인이 가능한 구슬을 모두 찾는다

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------

 

핵심은 한쪽에 추를 올리는 것이 +라고 한다면 반대쪽에 올리는 것은 -라고 생각하는 것이다

 

한쪽에 +4g을 올리면 다른 한쪽에 1g을 올릴때 -1g을 올린다고 생각하면 양쪽이 3g의 무게차이가 난다

 

이는 3g의 구슬을 올리면 균형을 맞출 수 있다는 뜻이 된다

 

비슷하게 한쪽에 -4g을 올리고, 또 -1g을 올리면 -5g이 되므로 양쪽이 5g의 무게 차이가 난다

 

이는 5g의 구슬을 올리면 균형을 맞출 수 있다는 뜻이 된다

 

가능한 추의 무게 a에 대하여

 

만들 수 있는 양쪽의 무게 차이 p에 대해 추를 한쪽에 올리면 p+a

 

다른 쪽에 올리면 p-a

 

현재 추만 저울에 올리면 a

 

3가지 경우를 계속 모아가면 된다

 

dp = set()

for a in A:
    
    new_dp = set(dp)
    
    for p in dp:
        
        new_dp.add(p+a)
        new_dp.add(abs(p-a))
    
    new_dp.add(a)
    
    dp = new_dp

 

 

이러면 dp에는 추를 이용해 만들 수 있는 양쪽의 무게 차이가 저장되어 있고

 

구슬의 무게를 순회하면서 가능한 양쪽의 무게차이가 존재하면 확인할 수 있는 구슬의 무게가 된다

 

for b in B:
    
    if b in dp:
        
        print('Y',end=' ')
    
    else:
        
        print('N',end= ' ')

 

 

평소에 아는? dp 이용해서 

 

dp[i] = 양팔 저울의 무게 차이가 i로 가능하면 1, 아니면 0

 

s = 추의 무게 합

 

이러면 -s ~ s까지 가능해야하는데 배열의 인덱스는 0이상의 수만 가능하므로

 

0~2s 범위로 두고, s를 0으로 둬서 s를 offset으로 두면 된다.

 

배낭문제임을 이용해서 추의 무게 a1,a2,...,an에 대하여

 

i = 2s,2s-1,...로 역방향 순회를 하는거지

 

dp[i-a] = 1이면 a를 담을 수 있으므로 dp[i] = 1

 

dp[i+a] =1이면 a를 담을 수 있으므로 dp[i] = 1

 

근데 이러면 틀리더라고

 

n = int(input())

A = list(map(int,input().split()))

m = int(input())

B = list(map(int,input().split()))

s = sum(A)

dp = [0]*(2*s+1)
dp[s] = 1

for a in A:
    
    for i in range(2*s,-1,-1):
        
        if i >= a and dp[i-a] == 1:

            dp[i] = 1
        
        if i+a <= 2*s and dp[i+a] == 1:
            
            dp[i] = 1

for b in B:
    
    if b > s:
        
        print('N',end= ' ')
    
    else:

        if dp[b+s] == 1:
        
            print('Y',end=' ')
    
        else:
        
            print('N',end=' ')

 

 

왜 틀리나 했더니

 

chatgpt피셜로 일반적인 배낭문제에는 한방향만 업데이트했는데

 

지금은 양방향으로 동시에 업데이트하다보니 여러번 되는 문제가 있나봐

 

그런가 그런것 같기도 하고

 

 

 

이런식으로 dp를 복사해야하는듯

 

이게 좀 어렵다

 

s = sum(A)

dp = [0]*(2*s+1)
dp[s] = 1

for a in A:
    
    new_dp = dp[:]
    
    for i in range(2*s+1):
        
        if i+a <= 2*s and dp[i+a] == 1:

            new_dp[i] = 1

        if i >= a and dp[i-a] == 1:
            
            new_dp[i] = 1
    
    dp = new_dp[:]

 

 

그리고 나서 구슬의 무게 b에 대해 offset을 이용해서 dp[b+s] = 1이면 b는 측정이 가능하다

 

 

for b in B:
    
    if b > s:
        
        print('N',end= ' ')
    
    else:

        if dp[b+s] == 1:
        
            print('Y',end=' ')
    
        else:
        
            print('N',end=' ')