3. 양팔저울(DFS)

문제-생략

 

문제풀이

import sys                              
sys.stdin=open("input.txt", "r")  
def DFS(L, sum): #L은 깊이 and G를 접근하는 인덱스
    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))

 

Hint 

▶ 추의 총합이 s가 나온다면, 1~s까지의 수가 만들어진다고 가정한다. 

 

▶ 전체 s가지의 수 중에서 추로 잴 수 있는 가지의 수를 뺀다. 그러면 물의 무게를 잴수 없는 가지 수가 나온다.

 

▶ set자료형을 써서 중복된 case를 제거한다.

 

▶트리의 전략 :  

         브랜치 3가지  :        좌측 : 더한다.            중앙: 뺀다.           우측: 아무것도 안한다.