[C/C++] 백준 17610번 - 양팔저울

문제

무게가 서로 다른 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(추 무게의 합) 사이에 있는 정수 중, 양팔 저울을 한번만 이용해서는 측정이 불가능한 경우의 수를 출력한다.

 

<코드>

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int n, bead, x, weight[14], ans, sum;
bool dp[14][2600001];

void solve(int i, int w)
{
	if (i > n || dp[i][w]) return;
	dp[i][w] = true;
	solve(i + 1, w + weight[i]);
	solve(i + 1, abs(w - weight[i]));
	solve(i + 1, w);
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> weight[i];
		sum += weight[i];
	}
	
	solve(0, 0);
	
	for (int i = 1; i <= sum; i++)
		if (dp[n][i] == false) ans++;

	cout << ans;
	
	
}

 

풀이 방법

 

<기본 아이디어>

1. 그릇쪽 저울에 추를 올려 놓는 경우
=> solve(i + 1, 현재 무게 + i번째 추 무게); 

2. 그릇 반대편쪽 저울에 추를 올려 놓는 경우
=> solve(i + 1, abs(현재 무게 - i번째 추 무게); 

3. 해당 추를 아무데도 올려 놓지 않는 경우
=> solve(i + 1, 현재 무게);

www.acmicpc.net/problem/17610

17610번: 양팔저울