KOI 1차 2019 중1- 양팔 저울 > 문제은행 : 정보올림피아드&알고리즘




3335 : 양팔 저울

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
93 회   
시도횟수
259 회   

문제

무게가 서로 다른 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)개 추 무게 g1, g2,…,gk 가 주어질 때, 1부터 S사이에 있는 정수 중, 

양팔 저울을 한 번만 이용하여서는 측정이 불가능한 경우의 수를 찾는 프로그램을 작성하고자 한다.

 

 


입력형식

입력의 첫 불에는 추의 개수를 나타내는 정수 k(2≤k≤13)가 주어진다.

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


출력형식

표준 출력으로 1부터 S(추 무게의 합) 사이에 있는 정수 중, 

양팔 저울을 한 번만 이용하여서는 측정이 불가능한 경우의 수를 출력하라. 

각 테스트 케이스에 대한 배점 정보와, 제약 조건은 다음과 같다.

 

  • 그룹1, 총 10점 상당의 테스트 케이스로 구성되어 있다. 3≤k≤5를 만족한다.
  • 그룹2, 총 40점 상당의 테스트 케이스로 구성되어 있다. 3≤k≤9를 만족한다.
  • 그룹3, 총 50점 상당의 테스트 케이스로 구성되어 있다. 추가적인 제약 조건이 없다.

입력 예

3
1 5 7

출력 예

2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP