백준 16987번 : 계란으로 계란치기 - 백트래킹 C++

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

16987번: 계란으로 계란치기

#include <bits/stdc++.h>

using namespace std;

struct Egg {
    int s, w;
};

Egg arr[8];

int N , ans;

void DFS(int cur) {
    if (cur == N) {
        int cnt = 0;
        //깨진 계란 갯수 확인하기
        for (int j = 0; j < N; j++) {
            if (arr[j].s <= 0) cnt++;
            ans = max(ans, cnt);
        }
        return;
    }

    for (int i = 0; i < N; i++) {
        if(i==cur) continue;
        //단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다.
        if (arr[cur].s <= 0 || arr[i].s <= 0){
            DFS(cur+1);
            continue;
        }
        //손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다.
        arr[i].s -= arr[cur].w;
        arr[cur].s -= arr[i].w;
        DFS(cur+1);
        arr[i].s += arr[cur].w;
        arr[cur].s += arr[i].w;
    }
}

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

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


    DFS(0);

    cout << ans << '\n';

    return 0;
}