백준(BOJ) 16987번 계란으로 계란치기

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

16987번: 계란으로 계란치기

풀이 :

제일 왼쪽 기준 계란을 시작으로 n-1개의 계란들 중 한 계란을 골라서 깨주어야 한다.

 

깰수있는 계란들 중 어느것을 골라서 깨느냐에 따라 정답이 달라지기 때문에 하나하나 모든 경우의

 

수를 다 처리 해주어야 한다. 이때 기준 계란이 깨져있을 경우나 혹은 선택하는 계란들이 모두 깨져있다면

 

다음 기준으로 곧바로 넘어감을 주의하자.

 

코드 ( C++ )

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int n;
	int dur[8];
	int w[8];
	int solve(int target)
	{
	if (target == n)
	{
	int sum = 0;
	for (int i = 0; i < n; ++i)
	if (dur[i] <= 0)
	sum++;
	return sum;
	}
	if (dur[target] <= 0)
	return solve(target + 1);
	bool check = false;
	int ret = 0;
	for (int cand = 0; cand < n; ++cand)
	{
	if (target == cand) continue;
	if (dur[cand] <= 0) continue;
	check = true;
	dur[target] -= w[cand];
	dur[cand] -= w[target];
	ret = max(ret, solve(target + 1));
	dur[target] += w[cand];
	dur[cand] += w[target];
	}
	if (!check)
	{
	return solve(target + 1);
	}
	return ret;
	}
	int main()
	{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
	cin >> dur[i] >> w[i];
	}
	cout << solve(0) << "\n";
	}

view raw .cpp hosted with ❤ by GitHub