[알고리즘] 양팔저울(DFS)

(문제) 양팔저울(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까지이다.

출력설명

첫 번째 측정이 불가능한 가지수를 출력하세요.

테스트케이스

입력예제	출력예제
3 1 5 7	2
5 4 7 10 22 25	12
8 2 4 8 16 32 64 128 256	255
8 1 2 4 8 16 32 64 128	0
9 8 13 21 34 55 89 144 233 377	699
10 1152 835 1351 21351 21353 5533 8359 10350 101 108	50650

---

해결방법

1. 총 개수 - 구할 수 있는 값 = 답

입력을 가지고 상태 트리 만들기

Node : 더하기, 빼기, 추 사용안하기

---

코드

def DFS(L, sum):
    if L == k:
        # 만들어 진 것들 중 0 이하 인 것들은 set 집합에 추가 안함
        if not sum <= 0:
            res.add(sum)

    # 3개의 구간 만들기
    else:
        # 추를 올린다 (더하기)
        DFS(L+1, sum+a[L])
        # 추를 반대쪽에 올린다 (빼기)
        DFS(L+1, sum-a[L])
        # 추를 올리지 않는다
        DFS(L+1, sum)


k = int(input())

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

# 집합으로 추로 구할 수 있는 무게의 경우의 수를 알아보기
# set을 이용항 이유는 중복 값을 없애기 때문
res = set()

DFS(0, 0)

print(sum(a)-len(res))