1. 문제설명

문제의 설명이 길기 때문에 필요한 정보만 요약하겠다.
계란으로 계란을 치려고 한다.
각 계란은 내구도(s)와 무게(w)가 있다.
계란으로 계란을 치면, 계란의 내구도는 상대 계란의 무게만큼 깎인다.
계란 치는 과정
- 가장 왼쪽의 계란을 든다.
- 들고 있는 계란으로 깨지지 않은 다른 계란 하나를 친다.
  - 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다.
- 들고 있는 계란이 가장 오른쪽에 위치한 계란이라면 종료한다.

2. 알고리즘 설계

DFS 문제이다.
1번부터 N번까지의 계란을 깬다.
- 시작점은 1, 2, 3, … 과 같이 오른쪽으로만 갈 수 있다.
- for(int i=0; i<n; i++)
무게만큼 내구도를 감소시켜주고,
- s[cnt] -= w[i], s[i] -= w[cnt]
내구도가 0 이하라면 카운팅한다.
- 중요한 건 이하라는 것이다. 음수값이 아닌!
- if(s <= 0) tmp++

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 10;
int n, s[SZ], w[SZ];
int tmp, mx;

void solve(int cnt) {
	if(cnt == n) {
		mx = max(mx, tmp);
		return;
	}

	if(s[cnt] <= 0 || tmp == n-1) {
		solve(cnt+1);
		return;
	}

	for(int i=0; i<n; i++) {
		if(s[i] <= 0 || i == cnt) continue;

		s[cnt] -= w[i];
		s[i] -= w[cnt];
		if(s[cnt] <= 0) tmp++;
		if(s[i] <= 0) tmp++;
		solve(cnt+1);
		if(s[cnt] <= 0) tmp--;
		if(s[i] <= 0) tmp--;
		s[cnt] += w[i];
		s[i] += w[cnt];
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for(int i=0; i<n; i++)
		cin >> s[i] >> w[i];
	
	solve(0);

	cout << mx;
    return 0;
}

4. 소감

위에 설명했듯이 0 이하가 되면 카운팅해야한다.
s < 0으로 코드를 작성해서 맞왜틀을 시전했다.
- 맞왜틀 : 맞는데 왜 틀리지

BOJ 16987. 계란으로 계란치기

1. 문제설명

2. 알고리즘 설계

3. 전체 코드

4. 소감