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

문제 링크

16987번: 계란으로 계란치기

문제 요약

N개의 계란이 있고, 각 계란은 내구도와 무게가 있다. 계란 두 개가 충돌하면 각 계란의 내구도는 상대 계란의 무게만큼 감소하게 된다. 아래와 같은 절차로 계란들을 충돌시켰을 때, 깨지는 최대 계란 수를 구해야 한다.
1. 가장 왼쪽의 계란을 든다.
2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.

접근 방법

백트래킹으로 접근할 수 있습니다.

기본적으로 N개의 계란을 순서대로 검사하면서, 깨지지 않은 계란이 있다면 충돌시킨 다음에 재귀 호출을 합니다. 만약 오른쪽 끝에 도달한다면 깨진 계란의 수를 세주고 리턴을 해주면 됩니다.

만약 함수가 호출되었을 때, 현재 계란이 깨진 상태라면 바로 다음 계란을 재귀호출을 해줍니다.

만약 충돌시킬 계란이 하나도 없는 경우에도 재귀호출을 해주면 됩니다

코드

#include <bits/stdc++.h>

using namespace std;

int n, ans;
vector<pair<int, int>> v;

void func(int now)
{
	if (now == n)
	{
		int cnt = 0;
		for (auto& i : v)
			if (i.first <= 0)
				cnt++;
		ans = max(ans, cnt);
		return;
	}

	if (v[now].first <= 0)
	{
		func(now + 1);
		return;
	}

	bool flag = false;
	for (int i = 0; i < n; i++)
	{
		if (i == now || v[i].first <= 0)
			continue;

		flag = true;
		v[now].first -= v[i].second;
		v[i].first -= v[now].second;
		func(now + 1);
		v[now].first += v[i].second;
		v[i].first += v[now].second;
	}

	if(!flag)
		func(now + 1);
}

int main(void)
{
	cin >> n;

	v.resize(n);
	for (int i = 0; i < n; i++)
		cin >> v[i].first >> v[i].second;

	func(0);
	cout << ans;
	return 0;
}