[파이썬 알고리즘 문제풀이] - Section7 / 깊이/넓이 우선 탐색(DFS, BFS ) 활용 - 3

양팔저울(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

import sys
# sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10000)

#추는 양쪾에 가능.
k = int(input())
data = list(map(int, input().split()))
S = sum(data)

res = set()
def DFS(L,sum):
    if L == k: #다 확인. 종료조건
        if sum > 0:
            res.add(sum)  #음수는 확인할 필요가 없음. 결국 양수랑 대칭을 이루기 때문.
    else:
        DFS(L+1, sum + data[L]) #해당 추 반대편
        DFS(L+1, sum) #사용 x
        DFS(L+1, sum - data[L]) #그릇 쪽에
DFS(0,0)
print(S - len(res))

코멘트

이 문제는 추의 각각을 부분집합에 포함할지 말지를 고민하는 문제였다.
근데 이 문제가 다른 점이 있다면. 속할지 말지 두 가지 기준이 있는게 아닌 !

• 왼쪽, 포함x, 오른쪽 총 3가지 상태트리 형태가 된다. (-무게, 무게포함x, +무게)

이걸 파악했으면 코드 짜는 것은 쉬웠다.