파이썬 알고리즘 057 | 양팔저울(DFS)

57. 양팔저울(DFS)

무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0
으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다.
주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고, 각 추의 무게가 {1, 2, 6}이
면, S=9이고, 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과
같이 그릇에 담을 수 있다. X는 그릇에 담는 물의 무게이고, ⎕은 그릇을 나타낸다.

만약 추의 무게가 {1, 5, 7}이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5,
6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담을
수 없다.
K(3<=K<=13)개의 추 무게가 주어지면, 1부터 S사이의 정수 중 측정이 불가능한 물의 무게는
몇 가지가 있는 지 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 K(3<=K<=13)이 주어집니다.
두 번째 줄에 K개의 각 추의 무게가 공백을 사이에 두고 주어집니다. 각 추의 무게는 1부터
200,000까지이다.
▣ 출력설명
첫 번째 측정이 불가능한 가지수를 출력하세요.
▣ 입력예제 1
3
1 5 7
▣ 출력예제 1
2

<내 풀이>

• 빼기로 나오는 값의 경우들은 어떻게 구하는지 모르겠음
  ===> ch[x]=0 / DFS(x+1), ch[x]=n[x] / DFS(x+1) 에다가 ch[x]=-n[x]도 설정해놓고 나중에 sum(ch)할 때 0보다 작은 애들은 제외해주면 된다

<처음에 안되던 것>

def DFS(x) : 
    if x==3:
        v[sum(ch)]=1
        print(v)
    else : 
        ch[x]=0
        DFS(x+1)
        ch[x]=n[x]
        DFS(x+1)
            
if __name__=='__main__' :
    a=[]
    k=int(input())
    n=list(map(int,input().split()))
    ss=sum(n)
    ch=[0]*(k)
    h=[0]*(k)
    v=[0]*(ss+1)
    DFS(0)

===> DFS(x+1) 에다가 ch[x]=-n[x] 추가해준 것
<이제 되는 것>

def DFS(x) : 
    if x==k:
        if sum(ch)>0:
            v[sum(ch)]=1
    else : 
        ch[x]=0
        DFS(x+1)
        ch[x]=n[x]
        DFS(x+1)
        ch[x]=-n[x]
        DFS(x+1)
if __name__=='__main__' :
    cnt=0
    a=[]
    k=int(input())
    n=list(map(int,input().split()))
    ss=sum(n)
    ch=[0]*(k)
    h=[0]*(k)
    v=[0]*(ss+1)
    DFS(0)
    
    for i in v:
        if i==0:
            cnt+=1
    print(cnt-1)
    

<풀이>

• 신기한 풀이법으로 접근하셨음
  
• 왼 / 오 / 놓지 않음
  의 경우로 나누면서 왼쪽에 놓으면 마이너스, 오른쪽에 놓으면 플러스, 놓지 않으면 그대로 의 경우로 나누어서 sum을 구해주기
• 다만 sum을 구하다가 마이너스 나오는 경우도 있는데 어차피 반대의 경우(양수)가 출력되기 때문에 굳이 음수 아이들은 세지 않아도 된다

def dfs(l,sum) :
    global res
    if l==n:
        if 0<sum<=s: #음수로 출력되는 건 나중에 양수로 대칭적으로 나와서 고려하지 않아도 된다
            res.add(sum)

    else :
        dfs(l+1, sum+g[l]) #추를 오른쪽에 놓는다
        dfs(l+1, sum-g[l]) #추를 왼쪽에 놓는다
        dfs(l+1, sum) #추를 무게 재는데 사용하지 않겠다

if __name__=='__main__' :
    n=int(input())
    g=list(map(int,input().split()))
    s=sum(g)
    res=set()
    dfs(0,0)
    print(s-len(res))

<반성점>

• 부분집합의 복습 필요 (체크리스트를 만들어서 ch[x]=0 / ch[x]=1 로 나누는 형식이 베이스)
• 새로운 사고방식의 필요

<배운 점>

<2차 내 풀이>

def dfs(x,s) :
    if x==n :
        if s>0:
            ch[s]=1
    else :
        dfs(x+1, s+a[x])
        dfs(x+1, s-a[x])
        dfs(x+1, s)

if __name__=='__main__' :
    n=int(input())
    a=list(map(int, input().split()))
    ch=[0]*(sum(a)+1)
    dfs(0,0)
cnt=0
for i in ch:
    if i==0:
        cnt+=1
print(cnt-1)