백준 g5 16987 계란으로 계란치기 c++

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

16987번: 계란으로 계란치기

 

문제 설명

• input
  • 계란의 내구도, 계란의 무게
• output
  • 깰 수 있는 계란 개수의 최대
• 규칙
  • 1. 맨 왼쪽의 계란을 든다.
  • 2. 깰 수 있는 계란 중 하나를 골라 계란을 부딪힌다. 이때 들고 있는 계란이 깨져있거나, 깰 수 있는 계란이 남아있지 않을 땐 그냥 넘어간다.
  • 3. 한 칸 오른쪽 계란을 들고, 2번을 반복한다.
  • 4. 맨 오른쪽 계란까지 수행했으면 끝낸다.

풀이

N <= 8으로 작은 편이므로, 모든 경우의 수를 살펴본다.

주의할 것은 계란 하나를 들었을 때 깰 수 있는 남은 계란이 없으면, 끝내지 말고 다음 계란을 들도록 넘어가야 한다. (func(cur+1))

 

코드

/*boj g5 16987 계란으로 계란치기*/
#include <iostream>
#define MAXN 10
using namespace std;

int N;
pair<int, int> egg[MAXN];
int mx = -1;

bool allBroken(int except) {
    for (int i = 0; i < N; i++) {
        if (i == except) continue;
        if (egg[i].first > 0) return false;
    }

    return true;
}

void func(int cur) {
    if (cur == N) {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            if (egg[i].first <= 0) sum++;
        }
        mx = max(mx, sum);
        return;
    }

    if (egg[cur].first < 0 || allBroken(cur)) {
        func(cur + 1);
        return;
    }

    for (int i = 0; i < N; i++) {
        if (i == cur) continue;
        if (egg[i].first < 0) continue;
        // 만약 남은 모든 계란이 깨져있으면,
        // 그냥 for문 돌다가 끝나는 것이 아닌 func(cur+1)을 수행해야 한다

        egg[cur].first -= egg[i].second;
        egg[i].first -= egg[cur].second;

        func(cur + 1);

        egg[cur].first += egg[i].second;
        egg[i].first += egg[cur].second;
    }
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;

    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        egg[i] = {a, b};
    }

    func(0);
    cout << mx << '\n';
}