양팔저울

생성일: 2022년 2월 10일 오후 2:20

구현 코드 ⭐

# 양팔저울
import sys
sys.stdin = open("input.txt", "rt")

def DFS(L, sum):
    global res
    if L == k:
        if 0<sum<=s:
            res.add(sum)
    else:
        DFS(L+1, sum+weight[L])
        DFS(L+1, sum-weight[L])
        DFS(L+1, sum)

if __name__ == "__main__":
    k = int(input())
    weight = list(map(int, input().split()))
    s = sum(weight)
    res = set()
    DFS(0, 0)
    print(s-len(res))

• 추가 왼쪽에 놓일 경우 sum에 추 무게를 더해주고 오른쪽에 놓일 경우에는 sum에 추 무게를 뺀다. 아예 해당 추를 안놓는 경우에는 그냥 sum을 그대로 넘겨준다.
• 모든 추들을 왼, 오, 놓지 않는 경우 ⇒ 이렇게 3가지 경우를 조사하면 결국 대칭 구조로 나오게 되는데 결과값이 음수, 양수인 경우로 대칭되게 된다. 절대값은 서로 같기 때문에 그 중에서 한개만 res에 추가해준다(양수인 경우)