[BOJ] 16987_계란으로 계란치기 with cpp

# 생각

모든 달걀을 다 돌아보면서 칠 수 있는 달걀이 있으면 내리치고 다음 단계로 넘어가는 문제이다

 

문제의 조건으로는 

가장 왼쪽 달걀로 시작한다

--> 어떤 달걀로 시작하냐에 따라 결과가 다르기 때문에 모든 경우의 수를 다 체크해야하고

--> 최대 개수를 출력해야 하므로 max값을 return해준다

 

손에 들고 있는 달걀이 안 깨져있고, 다른 달걀들 중 하나라도 달걀이 안 깨졌다면

달걀을 내려치고 그 다음 달걀을 손에 쥔다

--> depth번째 달걀이 깨져있거나 다른 모든 달걀이 이미 깨져있다면 패스해준다

 

가장 마지막 달걀이 될 때까지 달걀치기를 반복한다

--> 백트래킹으로 구현하되 현재 손에 든 달걀 또는 이미 깨진 달걀은 패스해준다

 

 

# 전체 코드

// 2s, 512MB
// 1 <= N <= 8
#include <bits/stdc++.h>
using namespace std;

int N, ans, cnt;
int s[8], w[8];

void funcRecursive(int depth, int st)
{
	if (depth == N)
	{
		ans = max(ans, cnt);
		return;
	}
	// depth번째 달걀이 깨져있거나 다른 모든 달걀이 깨져있다면 패스
	if (s[depth] <= 0 || cnt == N - 1)
	{
		funcRecursive(depth + 1, st);
		return;
	}
	// i번째 달걀 깨기
	for (int i = st; i < N; i++)
	{
		// 현재 손에 든 달걀 또는 이미 깨진 달걀은 패스
		if (i == depth or s[i] <= 0) continue;

		s[depth] -= w[i];
		s[i] -= w[depth];
		if (s[depth] <= 0) cnt++;
		if (s[i] <= 0) cnt++;
		funcRecursive(depth + 1, st);
		if (s[depth] <= 0) cnt--;
		if (s[i] <= 0) cnt--;
		s[depth] += w[i];
		s[i] += w[depth];
	}
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> s[i] >> w[i];
	}
	funcRecursive(0, 0);
	cout << ans;
}

 

---

 

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

16987번: 계란으로 계란치기