양팔저울 알고리즘(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

textcode :

1. input 받기
2. 변수 할당 및 준비
   s : 모든 추를 합한 값
   chk_dup : 1부터 s까지 사용 여부 확인. 해당 값이 들어가 있고, 0일 경우 사용된 값.
   cnt : 리턴할 cnt의 값을 s로 할당
   chk_use : 해당 추 사용 여부. 처음에 0(미사용)으로 초기화.
3. dfs로 다음 추로 넘어가면서 더하고, 만약 더한 값이 전에 나온 적 없으면 cnt--

0(미사용), 1(왼쪽_그릇과 함께 올리는 값) 2(오른쪽 비교값)으로 사용 여부를 확인
그래서 보통은 노드를 0,1로 사용, 미사용만 구분하는데 세 가지 경우를 다 따져서 해야 함

문제해결과정:

처음에는 추의 값을 더해서 나올 수 있는 순열 문제인줄 알았는데,
(찾는 무게+2):6 같은 값이 나올 수 있다.
따라서 현재 추보다 작은 추를 빼서 나올 수 있는 값도 다 더해야 한다.

def get_all_sum(d, sum):
    global cnt
    if sum_arr[sum] != 0:
        sum_arr[sum] = 0
        cnt -= 1
    if d >= n:
        return
    get_all_sum(d+1, sum+coin[d]) 
    get_all_sum(d+1, sum)
    if sum - coin[d] > 0 :
        get_all_sum(d-1, sum-coin[d])

그래서 마지막 2줄을 더했는데 여기에 안...걸려...
걸리지 않는 이유를 확인했더니, 이제까지의 값보다 현재 뎁스의 추가 더 큰 경우밖에 없었다...
1, 2, 6이 있을 경우 1, 2를 더한 상태로 넘어와 6과 비교하기 때문에 현재 추를 뺄 수가 없다...

그래서 문제를 다시 확인했는데, 지금 해당이 안 돼는 케이스가

이건데....
이건 단순히 더해가면서 풀 수가 없겠더라....
그래서 그냥 모든 노드 값을 체크해보기로 함 ㅎㅎ

import sys

n = int(sys.stdin.readline())
coin = list(map(int, sys.stdin.readline().split()))
s = sum(coin)
chk_dup = [i for i in range(s + 1)]
# 중복방지
cnt = s
# 리턴할 값
chk_use = [0] * (len(coin))
# 사용여부 chk : 0 = 미사용, 1 왼쪽, 2, 오른쪽

def get_all_sum(d):
    global cnt
    if d >= n:
        temp = 0
        for i in reversed(range(n)):
            if chk_use[i] == 1:
                temp -= coin[i]
            elif chk_use[i] == 2:
                temp += coin[i]
        # print(temp, chk_use)
        if temp > 0 and chk_dup[temp] > 0: 
            #1보다 큰 경우에는 무게가 존재 + 중복방지
            chk_dup[temp] = 0
            cnt -= 1
        return
    chk_use[d] = 2
    get_all_sum(d+1) 
    chk_use[d] = 1
    get_all_sum(d+1)
    chk_use[d] = 0
    get_all_sum(d+1)

get_all_sum(0)
print(cnt)

모든 노드를 검사하고, 무게가 존재할 경우 / 중복된 값이 아닐 경우에만 cnt를
내리도록 했는데...
타임아웃이 분명 어딘가에서 걸릴 것 같았는데 안 걸린다.
추의 갯수가 적어서 그런 듯..?
어쨌든 완성~!