[인프런] 양팔저울

문제

무게가 서로 다른 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): 추의 갯수
각 추의 무게는 1부터 200,000까지이다.

예제

3 (추의 갯수)
1 5 7 (각 추의 무게)

출력

첫 번째 측정이 불가능한 가짓수

예제

2

생각

문제를 처음에 바로 이해하지 못하여 문제를 이해하는데 시간이 조금 소요되었다. 문제는 결국 주어진 추를 + 혹은 - 연산을 어떻게든 하여서 나올 수 없는 경우의 수가 몇가지인가를 출력하는 것이다. 주어진 예제로 예를 들면

• 7 - 5 + 1 = 1 or 1 = 1
• 7 - 5 = 2
• 7 + 1 - 5 = 3
• 5 - 1 = 4
• 5 = 5
• 1 + 5 = 6
• 7 = 7
• 1 + 7 = 8
• 5 + 7 - 1 = 11
• 5 + 7 = 12
• 5 + 7 + 1 = 13

이렇게 해서 1~13 (주어진 추의 합)까지의 수 중에서 9, 10은 조합할 수 없어서 13 - 11가지의 경우의 수를 하여 2가 되는 것이다.
경우의 수를 골라야하기에 DFS를 사용하여 문제를 풀 수 있을 것 같았다. 하지만 모든 연산을 한 부분을 어떻게 구현해야할지 감이 잡히지 않았다. 이는 다음과 같이 풀 수 있었다.

Solution

• 각 추를 왼쪽에 놓는 경우, 오른쪽에 놓는 경우, 아예 놓지 않는 경우로 총 세가지의 경우로 각 노드마다 탐색을 진행한다.
• 왼쪽에 놓는 경우는 해당 추의 무게를 +, 오른쪽에 놓는 경우는 해당 추의 무게를 -, 놓지 않는 경우는 0에 대하여 각 연산을 진행하고 결괏값을 한 변수에 누적시켜서 진행한다.
• 이를 상태트리를 그려보면 확인할 수 있는것은 양수의 값과 음수의 값이 대칭해서 값이 생성된다는 것과 중복되는 값이 존재한다는 것이다.
• 따라서 중복되는 값을 제거하기 위해 set 자료구조를 사용하였고, 대칭 값이 발생하기 때문에 음수의 값은 제외하고 양수의 값만을 set에 넣어주었다.

  k = int(input())
  weight = list(map(int, input().split()))
  s = sum(weight)
  # 7   1 5 -> 1 , 1   x x -> 1 과 같이 중복이 생길 수 있음. 따라서 set 사용.
  ret = set()
  def dfs(level, sum):
    global ret
    if level == k:
        if 0 < sum <= s:
            ret.add(sum)
    else:
        dfs(level + 1, sum + weight[level])
        dfs(level + 1, sum - weight[level])
        dfs(level + 1, sum)
  dfs(0, 0)
  print(s - len(ret))