양팔저울
면접 대비시간 제한1초메모리 제한512 MB
서로 다른 무게추 13개 이하가 주어질 때, 각 추를 접시 쪽, 반대쪽, 사용 안 함 중 하나로 두어 만들 수 없는 1부터 전체 합까지의 정수 개수를 센다.
문제
무게가 서로 다른 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(3 ≤ k ≤ 13)가 주어진다. 다음 줄에 k개의 정수 gi(1 ≤ gi ≤ 200,000)가 공백으로 구분되어 주어지며, 각 값은 추의 무게이다.
출력
1부터 S(추 무게의 합)까지의 정수 중 양팔저울을 한 번만 이용해서는 측정할 수 없는 수의 개수를 출력한다.