백준 16987 계란으로 계란치기 (C++)

16987번: 계란으로 계란치기

백트래킹을 이용한 문제이다. 사실상 문제에서 조건들을 다 알려주었기에 조건대로 로직을 짜주면 된다. 가장 왼쪽 계란부터 시작하여 dfs를 시작한다. 반복문을 돌며 하나씩 비교해 내구도를 바꾸어주면서 깊이 탐색을 이용한다. 이때 더이상 깨지지 않은 다른 계란이 없다면 n == N 조건문에 걸리게 하기 위해 dfs(n + 1)을 해주고 최댓값을 구해주고 이를 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다. 백트래킹 문제를 좀 더 풀어봐야 겠다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, result = 0;
vector<pair<int, int>> v;

void dfs(int n) {
    if (n == N) {
        int tmp = 0;
        for (int i = 0; i < N; i++) {
            if (v[i].first <= 0) tmp++;
        }
        result = max(result, tmp);
        return;
    }
    if (v[n].first <= 0) {
        dfs(n + 1);
        return;
    }

    bool tf = false;
    for (int i = 0; i < N; i++) {
        if (n == i) continue;
        if (v[i].first <= 0) continue;

        tf = true;
        v[i].first -= v[n].second;
        v[n].first -= v[i].second;
        dfs(n + 1);
        v[i].first += v[n].second;
        v[n].first += v[i].second;
    }

    if (!tf) dfs(n + 1);
}

void solution() {
    dfs(0);

    cout << result;
}

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

    cin >> N;

    int S, W;
    for (int i = 0; i < N; i++) {
        cin >> S >> W;
        v.push_back({ S,W });
    }

    solution();

    return 0;
}