Python 27제] 2019년 한국정보올림피아드 1차대회 2교시 중등부 유형3. 1번-양팔 저울

출처 : 반크 2021년 10월 25일 독도의 날 포스터

 

무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔 저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고 그 무게가 각각 {1, 2, 6}이며, S=9이고, 양팔 저울을 한 번만 이용하여 1부터 S사이 모든 정수에 대응하는 물을 다음과 같이 그릇에 담을 수 있다. 여기서 X는 그릇에 담는 물의 무게를 나타내고, □는 그릇을 나타낸다.

 

만약 추의 무게가 {1, 5, 7}이면 S=13이 되고, 양팔저울을 한 번만 사용하여 그릇에 담을 수 있는 무게는 {1, 2, 3, 4, 5, 5, 7, 8, 11, 12, 13}이다. 즉, 1부터 S사이 수 가운데 9와 10에 대응하는 무게의 물을 그릇에 담는 것은 불가능하다.

 

k(3≤ k ≤13)개 추 무게 g1, g2, ..., gk가 주어질 때, 1부터 S사이에 있는 정수 중, 양팔저울을 한 번만 이용하여서는 측정이 불가능한 경위의 수를 찾는 프로그램을 작성하고자 한다.

 

 

입력 형식

입력의 첫 줄에는 추의 개수를 나타내는 정수 k(3≤ k ≤13)가 주어진다. 다음 줄에는 k개의 정수 gi(3≤ i ≤k)(1≤ gi ≤200,000)가 공백으로 구분되어 주어지는데 이는 각 추의 무게를 나타낸다.

 

출력 형식

표준 출력으로 1부터 S(추의 무게의 합) 사이에 있는 정수 중, 양팔 저울을 한 번만 이용하여서는 측정이 불가능한 경우의 수를 출력하라.

 

 

입/출력 예시]

입력 1

3

1 5 7

 

출력1

2

 

 

출처 : 한국정보올림피아드 2019년 중등부 1차대회 2교시

 

 

참고풀이]

import sys #exit()

def dfs(x,s):
    if x==N:
        if 0<s<=t:
            L.add(s)
    else:
        dfs(x+1,s-g[x])
        dfs(x+1,s)
        dfs(x+1,s+g[x])
    

#L이라는 집합을 선언한다.
L = set()

#입력될 추의 개수를 입력받는다.
N = int(input())
if 3<=N<=13:
    #N개의 추 무게를 입력받는다.
    g = list(map(int, input().split()))
    #N개의 추의 무게중 범위를 벗어나는 추가 있으면 작업을 중지한다.
    for a in g:
        if a<1 or a>200000:
            sys.exit()
    #입력된 추의 합을 구한다.
    t = sum(g)
    
    #깊이우선탐색을 활용하여 추무게들을 구한다.
    dfs(0, 0)
    
    #결과 출력
    print(t - len(L))

 

 

참고 풀이 결과]

 

 

 

대한민국의 아름다운 영토, 독도의 겨울