BOJ 16987 - 계란으로 계란치기

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

16987번: 계란으로 계란치기

 

접근 방법

전형적인 백트래킹 문제이다.

 

순서대로 계란을 집어, 나머지 계란 중 하나를 치면 되는 문제이다.

이 문제의 핵심은 조건문을 어떻게 작성하냐 이다.

 

내가 틀렸던 예제는 다음과 같다.

3
1 4
8 1
3 1

// 정답: 2

 

손에 든 계란 외에 모든 계란이 깨진 경우를 체크해주지 않아 답이 1이 나왔다.

이를 bool flag를 통해 쉽게 수정하였다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX 10

int n;
vector<pair<int, int>> v;
int used[MAX];
int res;

void func(int idx, int cnt) {

	if (idx >= (n+1)) {
		res = max(res, cnt);
		return;
	}

	// 자신이 깨졌으면 패스
	if (used[idx] < 1) {
		func(idx + 1, cnt);
	}
	else{
		bool flag = false;
		for (int i = 1; i <= n; i++) {
			// 자기 자신이거나 내구도가 0이하이면 패스
			if (i == idx || used[i] < 1) {
				continue;
			}

			// 계란 치고 백트래킹
			else {
				used[i] -= v[idx].second;
				used[idx] -= v[i].second;
				if (used[i] < 1 && used[idx] < 1) {
					// 둘 다 깨진 경우
					func(idx + 1, cnt + 2);
				}

				else if (used[i] < 1) {
					// 나머지 중 하나가 깨진 경우
					func(idx + 1, cnt + 1);
				}

				else if (used[idx] < 1) {
					// 들고 있는 것이 깨진 경우
					func(idx + 1, cnt + 1);
				}

				else {
					// 둘 다 깨지지 않은 경우
					func(idx + 1, cnt);
				}
				flag = true;
				used[i] += v[idx].second;
				used[idx] += v[i].second;
			}
		}

		// 들고 있는 계란 외에 모두 깨진 경우
		if (!flag)	func(n + 1, cnt);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	v.push_back(make_pair(0, 0));
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(a, b));
		used[i] = a;
	}

	func(1, 0);
	cout << res;
}