백준 16987번 계란으로 계란치기 C++

출처 : https://www.acmicpc.net/problem/16987

백트래킹을 이용하여 가능한 모든 경우를 구하고 그 경우들 중에서 계란이 가장 많이 깨진 개수를 구하면 된다.

처음에 문제를 풀때 현재 잡은 계란의 오른쪽 계란만 깰 수 있다고 생각하고 풀어서 답이 안나왔다.

그래서 문제를 다시 읽어보니 그런 조건이 없어서 모든 경우를 탐색하도록 바꿨더니 문제가 풀렸다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n;
vector<pair<pair<int, int>, int>> v(8);
int ans = 0;

void BT(int index) {
	if (index >= n) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			if (!v[i].second) cnt++;
			ans = max(ans, cnt);
		}
		return;
	}
	if (v[index].second == false) {
		BT(index + 1);
		return;
	}
	bool isAllBreak = true;
	for (int i = 0; i < n; i++) {
		if (i == index) continue;
		if (v[i].second) {
			isAllBreak = false;
		}
	}
	if (isAllBreak) {
		BT(index + 1);
		return;
	}
	int lastS = v[index].first.first;
	int lastW = v[index].first.second;
	for (int i = 0; i < n; i++) {
		if (i == index) continue;
		if (v[i].second == false) {
			continue;
		}
		int lastS2 = v[i].first.first;
		int lastW2 = v[i].first.second;
		v[index].first.first -= v[i].first.second;
		v[i].first.first -= v[index].first.second;
		if (v[i].first.first <= 0) {
			v[i].first.first = 0;
			v[i].second = false;
		}
		if (v[index].first.first <= 0) {
			v[index].first.first = 0;
			v[index].second = false;
		}
		BT(index + 1);
		v[index].first.first = lastS;
		v[index].first.second = lastW;
		v[index].second = true;
		v[i].first.first = lastS2;
		v[i].first.second = lastW2;
		v[i].second = true;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int s, w;
		cin >> s >> w;
		v[i].first.first = s;
		v[i].first.second = w;
		v[i].second = true;
	}
	BT(0);
	cout << ans;
};