문제 푼 날짜 : 2021-12-03

문제

문제 링크 : https://www.acmicpc.net/problem/16987

접근 및 풀이

문제가 이해가 안돼서 푸는 데 좀 오래걸린 문제였다.
백트래킹을 이용하였고, 매개변수로 각 계란의 index값(코드 내의 idx 변수)을 넘겨주었다.
이 때, idx는 손에 쥔 계란의 index를 뜻하며, 마지막 계란을 쥐었을 때 깨진 계란의 개수를 세어주었다.
깰 계란이 없을 때 마지막 계란을 들게하는 것이 포인트였다.(라고 개인적으로 생각한다...)

코드

// 백준 16987번 : 계란으로 계란치기
#include <bits/stdc++.h>

using namespace std;

int N, ans = -1;
vector<pair<int, int>> v;

void dfs(int idx) {
    if (idx == N) {
        int cnt = 0;
        for (int i = 0; i < v.size(); i++) {
            if (v[i].first <= 0) {
                cnt++;
            }
        }
        ans = max(ans, cnt);
        return;
    }
    if (v[idx].first <= 0) { // 손에 쥔 계란이 깨진 경우
        dfs(idx + 1);
    } else {
        bool broken = false;
        for (int j = 0; j < v.size(); j++) {
            if (j == idx || v[j].first <= 0) { // 손에 쥔 계란, 깨진 계란 pass
                continue;
            }
            broken = true;
            v[j].first -= v[idx].second;
            v[idx].first -= v[j].second;
            dfs(idx + 1);
            v[j].first += v[idx].second;
            v[idx].first += v[j].second;
        }
        if (!broken) { // 깰게 없으면 마지막 계란으로
            dfs(N);
        }
    }
}

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

    cin >> N;
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }
    dfs(0);
    cout << ans;
    return 0;
}

결과

피드백

다시 열심히 하자.