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

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

양팔 저울 timer 2s memory 512MB

양팔 저울 2s 512MB