Algorithm/acmicpc.net/source/16987.cpp at master · tdm1223/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// 16987. 계란으로 계란치기
// 2019.05.22
// 브루트 포스
#include<iostream>
#include<algorithm>

using namespace std;

int n;
egg eggs[9];
int realAns;
int ans;

struct egg
{
	int index; // 계란 번호
	int s; // 내구도
	int w; // 무게
	bool flag; //깨짐유무
	egg(int index, int s, int w, int flag) :index(index), s(s), w(w), flag(flag) {}
	egg() {}
};

// a달걀로 b를 때림
void Attack(egg& a, egg& b)
{
	a.s -= b.w;
	b.s -= a.w;
	if (a.s <= 0)
	{
		a.flag = true;
		ans++;
	}
	if (b.s <= 0)
	{
		b.flag = true;
		ans++;
	}
}

void Simulate(int cnt)
{
	if (cnt == n)
	{
		if (realAns < ans)
		{
			realAns = ans;
		}
		return;
	}

	// 현재 픽한 달걀이 깨지지 않았을 경우
	if (eggs[cnt].flag == false)
	{
		for (int i = 0; i < n; i++)
		{
			if (!eggs[i].flag && i != cnt)
			{

				Attack(eggs[cnt], eggs[i]);
				Simulate(cnt + 1);
				if (eggs[cnt].s <= 0)
				{
					eggs[cnt].flag = false;
					ans--;
				}
				if (eggs[i].s <= 0)
				{
					eggs[i].flag = false;
					ans--;
				}
				eggs[cnt].s += eggs[i].w;
				eggs[i].s += eggs[cnt].w;
			}
			// 치려는 달걀이 깨져있을때
			else if (eggs[i].flag && i != cnt)
			{
				Simulate(cnt + 1);
			}

		}
	}
	// 현재 픽한 달걀이 깨졌을 경우
	else
	{
		Simulate(cnt + 1);
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int s, w;
		cin >> s >> w;
		eggs[i] = egg(i, s, w, false);
	}

	Simulate(0);
	cout << realAns << endl;
	return 0;
}