[BOJ] 17610번 양팔저울 (C++)

풀이 소요시간 : 60분 초과 (실패)

조합 구하기 유형으로 착각하고 삽질을 하다가 말아먹었다. 물론 능력이 있었다면 해당 방식으로 풀어냈겠으나, 그러지 못했다. DFS 완전탐색으로 풀어낼 수 있는 문제다.

K(3 <= K <= 13) 의 범위를 가진 추의 갯수 K 가 주어진다.
K 개의 추를 1번 - K번의 순서대로 지나갈때 다음과 같은 3가지 상황이 주어진다.

1. n번째 추를 저울에 올리지 않고 n+1 번째 추로 넘어간다.
2. n번째 추를 추 그릇에 올리고 n+1 번째 추로 넘어간다.
3. n번째 추를 물 담는 그릇에 올리고 n+1 번째 추로 넘어간다.

2번째 상황의 경우 기존 추 그릇에 A kg 의 추가 담겨있고, n 번째 추가 B kg 이라고 가정할 때 추 그릇의 무게는 A+B kg 이 되고, 수평을 맞추기 위한 물의 무게는 A+B kg 이다. 이는 X = A+B 의 경우를 탐색한다는 의미가 된다.

3번째 상황의 경우 기존 추 그릇에 A kg 의 추가 담겨있고, n 번째 추가 B kg 이라고 가정할 때 수평을 맞추기 위한 물의 무게는 A-B kg 이고, 이는 X = A-B 의 경우를 탐색한다는 의미가 된다.

전체 코드(DFS)

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

int N;
int Map[14];
int Cnt = 0;
int S = 0;

vector<bool> Measure;

void Fast_IO() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> Map[i];
		S += Map[i];
	}
	Measure.resize(S + 1, false);
	// 방문 여부를 저장하는 Vector(동적 할당) Measure[1] - Measure[S]
}

//0. 넘어가는 순서 1 -> N 차례대로 진행한다.
//1. 해당 추를 올리지 않고 넘어간다.
//2. 해당 추를 올리고 넘어간다. X = A+B
//3. 해당 추를 반대편에 올리고 넘어간다. X = A-B
void Dfs(int count, int weight) {	
	if (count == N + 1) {
		if (weight > 0) {
			Measure[weight] = true;
		}
		return;
	}

	Dfs(count + 1, weight);
	Dfs(count + 1, weight + Map[count]);
	Dfs(count + 1, weight - Map[count]);
}


int main() {
	Fast_IO();
	Input();
	Dfs(1, 0);
	for (int i = 1; i <= S; i++) {
		if (Measure[i] == false) {
			Cnt++;
		}
	}
	cout << Cnt << '\n';
}