정올 양팔저울

문제

예제

 

k = int(input())
weight = list(map(int, input().split()))
S = sum(weight)
dp = [False] * (S+1)

def solve(i, w):
    if i == k:
        if 0 < w <= S:
            dp[w] = True
    else:
        solve(i + 1, w + weight[i])
        solve(i + 1, w - weight[i])
        solve(i + 1, w)

solve(0, 0)
ans = 0
for chk in dp[1:]:
    if not chk:
        ans += 1

print(ans)

 

이 코드는 주어진 추들을 사용해 양팔 저울로 측정할 수 없는 무게의 개수를 계산하는 프로그램이다. 각 추를 올리거나 내리거나 사용하지 않는 세 가지 선택을 재귀적으로 탐색하여 만들 수 있는 모든 양의 무게 조합을 구한다. 그런 다음 1부터 추들의 합까지의 무게 중에서 측정할 수 없는 무게의 개수를 출력한다.

 

import sys
input = sys.stdin.readline

def f(x,y):
    global A
    if x == k:
        if y <= B and y > 0:
            A.add(y)
    else:
        f(x+1,y-li[x])
        f(x+1,y)
        f(x+1,y+li[x])

k = int(input())
li = list(map(int,input().split()))
B = sum(li)
A = set()
f(0,0)

print(B-len(A))

 

이 코드는 주어진 정수 리스트에서 각 원소를 더하거나 빼거나 무시하는 방식으로 만들 수 있는 모든 양의 정수를 구한 뒤,

만들 수 없는 수가 몇 개인지를 계산하는 코드다.

 

재귀 함수 f(x, y)는 현재 몇 번째 원소를 보고 있는지(x)와 지금까지의 합(y)을 기준으로 세 가지 경우, 더하기, 빼기, 무시하기를 재귀적으로 탐색하며,

그 과정에서 0보다 크고 전체 합(B) 이하인 값들을 집합 A에 저장한다.

 

모든 경우의 수를 확인한 뒤,

전체 가능한 합 B에서 실제로 만들 수 있었던 수의 개수 len(A)를 빼서 만들 수 없는 수의 개수를 출력한다.