양팔 저울 > 문제은행



문제은행

3335 : 양팔 저울

제한시간: 2Sec    메모리제한: 512mb
해결횟수: 105회    시도횟수: 290회   



 

무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다.

양팔 저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다.

주어진 모든 추 무게의 합을 S라 하자. 

예를 들어, 추가 3개 이고 그 무게가 각각 {1,2,6} 이면, S = 9이고, 

양팔 저울을 한 번만 이용하여 1부터 S사이의 모든 정수에 대응하는 물을 다음과 같이 그릇에 담을 수 있다. 

여기서 X는 그릇에 담는 물의 무게를 나타내고, □는 그릇을 나타낸다.

 

4070e241f6131e5c9ebab06998edc460_1557126

 

만약 추의 무게가 {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점 상당의 테스트 케이스로 구성되어 있다. 추가적인 제약 조건이 없다.

  • [Copy]
    3
    1 5 7
    [Copy]
    2






    HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
    경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
    Copyright@2010-2015 jungol. All right reserved.