백준17610 양팔저울

작성일 | In

문제 출처

  • 2019 KOI 1차 중등부 1번

사용 알고리즘

  • 완전 탐색

시간복잡도

  • O(3k)

풀이

각 원소는

  • 왼쪽 저울에 올라감
  • 오른쪽 저울에 올라감
  • 저울에 안 올라감

총 3가지 상태 중 하나를 갖고 있습니다.

k <= 13이므로 3k개의 경우를 모두 돌려주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

int v[22];
int chk[3030303];
int bit[22];
int k, s, ans;

void f(int dep){
	if(dep == k){
		int a = 0, b = 0;
		for(int i=0; i<k; i++){
			if(bit[i] == 1) a += v[i];
			if(bit[i] == 2) b += v[i];
		}
		if(a < b) swap(a, b);
		chk[a-b] = 1;
		return;
	}
	for(int i=0; i<3; i++){
		bit[dep] = i;
		f(dep+1);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> k;
	for(int i=0; i<k; i++) cin >> v[i], s += v[i];
	f(0);
	for(int i=1; i<=s; i++){
		ans += !chk[i];
	}
	cout << ans << "\n";
}