BaekJoon 16987번: 계란으로 계란치기(C++)

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

16987번: 계란으로 계란치기

풀이법

1) 백트래킹과 구현이 합쳐진 문제로서 해결함에 있어 시간이 오래걸렸다. (일단 문제에 필요 없는 tmi가 너무 많았다 ㅠㅠ)

2) 왼쪽부터 차례대로 탐색한다는 것이 가장 중요했으며, 구현을 위해 현재 계란의 내구도가 0보다 작을 경우, 깰 수 있는 다른 계란이 남지 않았을 경우를 if문으로 명시하였다.

3) 서로의 무게로 계란을 깬 이후 깨진 계란 만큼 수를 추가시켜 주었고 백트래킹을 이용해서 반복하여 결과를 낼 수 있었다. (0이하를 미만으로 생각했다가 틀렸습니다 폭탄이 나왔다.. 문제를 잘 읽자)

 

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<pair<int, int>> vec;
int n;
int ans = 0;
bool check(int index)
{
	for (int i = 0; i < n; i++)
	{
		if (index == i)
			continue;
		if (vec[i].first > 0)
			return false;
	}
	return true;
}
void backtracking(int index, int cnt)
{
	if (index == n) {
		ans = max(ans, cnt);
		return;
	}
	if (vec[index].first <= 0 || check(index))
		backtracking(index + 1, cnt);
	else
	{
		for (int i = 0; i < n; i++)
		{
			if (index != i && vec[i].first > 0)
			{
				vec[i].first -= vec[index].second;
				vec[index].first -=  vec[i].second;
				int nextcnt = cnt;
				if (vec[i].first <= 0)
					nextcnt++;
				if (vec[index].first <= 0)
					nextcnt++;
				backtracking(index + 1, nextcnt);
				vec[i].first += vec[index].second;
				vec[index].first += vec[i].second;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b; cin >> a >> b;
		vec.push_back({ a,b });
	}
	backtracking(0, 0); //왼쪽부터 차례로 한번씩만 든다. 최대한 많은 계란을 깬다.
	cout << ans;
}