[백준] 16987번

💻 C++ 기반

계란으로 계란치기
https://www.acmicpc.net/problem/16987

✔️ 내구도가 0 이하(0 포함)면 깨진다는 조건을 잘 파악하자!
✔️ 아래 코드에서 사실상 isBroken도 없어도 되고, func 함수의 인자로 cnt가 들어갈 필요도 없다.

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

#define MAX 9

using namespace std;

int N;
vector<pair<int, int> > v;
bool isBroken[MAX];
int ans = 0;

void func(int cur, int cnt)
{
    if (cur == N)
    {
        ans = max(ans, cnt);
        return;
    }

    if (isBroken[cur])
    {
        func(cur + 1, cnt);
        return;
    }
    
    bool flag = false;
    for (int i = 0; i < N; i++)
    {
        int nextCnt = cnt;
        if (!isBroken[i] && i != cur)
        {
            flag = true;
            int curS = v[cur].first;
            int curW = v[cur].second;

            int targetS = v[i].first;
            int targetW = v[i].second;

            v[cur].first -= targetW;
            v[i].first -= curW;
            if (targetS - curW <= 0)
            {
                isBroken[i] = true;
                nextCnt++;
            }
            if (curS - targetW <= 0)
            {
                isBroken[cur] = true;
                nextCnt++;
            }

            func(cur + 1, nextCnt);

            v[cur].first += targetW;
            v[i].first += curW;
            isBroken[i] = false;
            isBroken[cur] = false;
        }
    }
    if (!flag)
    {
        func(cur + 1, cnt);
    }
}

int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        int s, w;
        scanf("%d %d", &s, &w);
        v.push_back(make_pair(s, w));
    }

    func(0, 0);
    printf("%d", ans);
    return 0;
}