백준 BOJ 17610 - 양팔저울

https://www.acmicpc.net/problem/17610

17610번: 양팔저울

KOI 2019 중등부 1번

브루트포싱 문제였습니다.

단순하게 어떠한 추에 대해서 생각해볼 수 있는 세가지 경우

1. 왼쪽에 놓는다
2. 오른쪽에 놓는다
3. 저울에 올리지 않는다

 

이 셋을 모두 고려해서 소스코드를 작성해주면 된다

전체 시간복잡도는 O(3^N)인데, N이 13으로 매우 작아서 160만번 정도밖에

계산하지 않는다.

 

왼쪽에 놓는 경우에 측정 가능한 무게 K (지문에서는 □로 표기) 는 줄어들게 되므로,

오른쪽에 놓는 경우에는 K에 값을 더한다면

왼쪽에 놓는 경우에는 K에서 값을 빼내주면 된다.

이때 측정중인 무게 K가 음수까지도 내려갈 수 있으므로

std::map 을 사용하던지, 아니면 양수 인덱스에 대해서만 체크해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> g;
map<int,int> m;

void dfs(int w, int idx){
	if(idx == N+1) return;
	m[w] = 1;
	
	dfs(w+g[idx], idx+1);
	dfs(w-g[idx], idx+1);
	dfs(w, idx+1);
	return;
}

int main(){
	int k;
	int S=0;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> k;
		g.push_back(k);
		S += k;
	}
	
	dfs(0,0);
	
	int ans = 0;
	for(int i=1; i<=S; i++){
		if(m.find(i) == m.end()) ans++; 
	}
	cout << ans;
	return 0;
}