[알고리즘] C++ 백준 16987 계란으로 계란치기

 

백준 16987

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

16987번: 계란으로 계란치기

 

풀이 전 나의 생각

백트래킹을 사용하여 풀 수 있는 문제지만 조건을 잘 걸어놔야만 정확한 결과를 얻을 수 있다.

 

우선 재귀함수가 어떤 방식으로 진행되야 할지 미리 파악해야 한다.

 

1. 계란의 내구도가 존재하여 다른 계란을 깰 수 있는 경우

2. 계란이 깨져서 더 이상 다른 계란을 깰 수 없는 경우

3. 계란의 내구도가 존재하지만 다른 계란이 다 깨져 있는 경우

 

이렇게 3가지의 경우를 생각해서 코드를 구현하면 된다.

 

1번의 경우는 정상적으로 백트래킹을 진행하면 된다.

2번의 경우 더 이상을 계란을 깰 수 없다는 것은 그냥 다음 계란으로 순번을 넘기는 것을 의미한다.

즉, 더 이상 탐색을 진행할 수 없다는 뜻이 되니 바로 다음 순번의 재귀를 진행하면 된다.

3번의 경우를 예를 들어서 5개의 계란이 있다고 가정하자. 1번 계란이 2번 계란을 쳐서 둘다 뿌셔졌다. 그 다음으로 2번계란은 깨져서 그냥 넘어갔고 3번계란이 5번계란을 쳐서 둘다 뿌셔졌다. 그럼 이제 4번 계란이

다른 계란을 쳐야한다. 하지만 다른 계란들은 모두 뿌셔졌기 때문에 진행을 할 수가 없다. 그래서 바로 다음 순번의 5번 계란으로 재귀를 진행한다. -> 왜냐하면 최대 탐색 횟수까지 도달한 후 최대값을 반환해야 되기 때문이다.

풀이

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

using namespace std;

int n, res = 0;
pair<int, int> arr[9];

void DFS(int nEgg)
{
	if (nEgg == n)
	{
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			if (arr[i].first <= 0) cnt++;			
		}
		res = max(res, cnt);
		return;
	}

	if (arr[nEgg].first <= 0)
	{
		DFS(nEgg + 1);
		return;
	}

	bool isCrack = false;
	for (int i = 0; i < n; i++)
	{
		if (i == nEgg || arr[i].first <= 0) continue;

		isCrack = true;
		arr[nEgg].first -= arr[i].second;
		arr[i].first -= arr[nEgg].second;
		DFS(nEgg + 1);
		arr[nEgg].first += arr[i].second;
		arr[i].first += arr[nEgg].second;
	}

	if (!isCrack) DFS(nEgg + 1);
}

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

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i].first >> arr[i].second;
	}

	DFS(0);

	cout << res;
}