[인프런] 양팔저울

---

문제설명

무게가 서로 다른 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,00까지이다.

출력조건

• 첫 줄에 측정이 불가능한 가지수를 출력해라.

사고과정

• 처음에 문제를 무슨말인가..? 싶었다. 연습장에 그리면서 입력 예시로 생각해보았고 결국 주어진 추 숫자들을 가지고 + 또는 - 연산을 가지고 만들 수 있는 경우의 수를 모두 탐색한 후, 그 중 1 ~ S 사이에 없는 가지수를 출력하면 된다고 생각했다.
• 그래서 우선은 추들 중에서 추 1개부터 추 전채 개수 K까지 부분집합을 구하고 각 부분집합에 대해서 +,-가 들어갈 수 있는 중복을 허용한 순열을 구하는 경우의 수를 DFS 탐색했다. 결국 2번의 DFS 재귀함수를 사용해야 한다고 생각했다..
• 어쨌건 시간이 좀 걸렸지만 DFS 두개를 활용해 구현했다..!
• 풀이를 보니, 역시 한 번의 DFS로 풀 수 있었다. 상태 트리를 만드는 아이디어가 기발했는데, 상태트리의 레벨을 추의 index로 설정하고, 갈래를 뻗어나가는데 3가지 갈래를 뻗어나간다. 하나는 왼쪽에 추를 놓는 경우므로 추를 더해주고 , 하나는 오른쪽에 추를 놓는 경우라서 추를 빼준다, 그리고 마지막엔 추를 놓지 않는 경우를 둔다. 이렇게 하면서 상태트리 레벨이 추의 개수랑 같아졌을 때, 누적 합 즉, 만들 수 있는 물의 무게가 양수이면서 S보다 작거나 같으면 set()에 추가해준다. 이 때 음수를 절댓값으로 바꾸어서 포함해주어도 되긴 하는데, 음수는 어차피 다른 갈래에서 탐색할 것이기 때문에 제외해도 된다!
• 역시 간결한 코드는 대단하다.. 그래도 스스로 해결했다는 것에 의미를 두어야지..

풀이

- 강의 속 풀이(권장! 한 번만의 DFS 탐색 수행)

k = int(input())
G = list(map(int, input().split()))
s = sum(G)
res = set()


def DFS(L, sum):
    global res
    if L == k:
        if 0 < sum <= s:  # 음수는 어차피 다른 가지에서 똑같은 양수로 탐색하므로 음수는 탐색 X
            res.add(sum)
    else:
        DFS(L + 1, sum + G[L])
        DFS(L + 1, sum - G[L])
        DFS(L + 1, sum)


DFS(0, 0)  # 추 인덱스, 측정 가능한 물 무게
print(s - len(res))

- 나의 풀이(2번의 DFS 탐색 수행)

k = int(input())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
check = [0] * k
subset = []
def dfs(L):
    if L == k:
        res = []
        for i in range(k):
            if check[i] == 1:
                res.append(arr[i])
        if res:
            subset.append(res)
        return
    else:
        check[L] = 1
        dfs(L+1)
        check[L] = 0
        dfs(L+1)
dfs(L=0)
#print(subset)

def calc(L, sum_val, lst):
    global count
    if L == len(lst)-1:
        count[abs(sum_val)] = 1
        return
    else:
        calc(L+1, sum_val + lst[L+1], lst)
        calc(L+1, sum_val - lst[L+1], lst)

count = [0] * (sum(arr) + 1)
for x in subset:
    if len(x) == 1:
        count[x[0]] = 1
    else:
        calc(L=0, sum_val=x[0], lst=x)
answer = 0
for i in range(1, len(count)):
    if count[i] == 0:
        #print(i, end=' ')
        answer += 1
print(answer)