[DFS] BJ16987 계란으로 계란치기

문제 출처: https://www.acmicpc.net/problem/16987

 

Solution

• DFS를 하며 다음 계란을 모든 계란 중 하나를 골라 현재 계란과 쳐서 내구도를 업데이트 한 뒤 깨진 계란 개수를 업데이트해 나간다.

Point

• 현재 계란과 부딪힐 계란을 고를 때 해당 계란을 제외한 모든 깨지지 않은 계란이 후보가 될 수 있다.
• 현재 계란이 깨졌을 경우 그냥 다음 계란으로 넘어가야 한다.
• 깨진 계란 개수를 세는 것이 은근히 까다로웠는데, DFS 리턴할 때 깨진 계란의 개수를 롤백해줬다.

---

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

using namespace std;

int N;
struct egg { int s, w; };
vector<egg> list;
int result = 0;
int tmp_result = 0;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int s, w;
        cin >> s >> w;
        list.push_back({ s, w });
    }
}

void dfs (int d) {
    if (d == N) return;
    for (int i = 0; i < list.size( ); i++) {
        if (d == i) continue;
        if (list[i].s <= 0) continue; //next egg broken
        if (list[d].s <= 0) { //cur egg broken
            dfs(d + 1);
        }
        else {
            list[d].s -= list[i].w;
            list[i].s -= list[d].w;
            if (list[d].s <= 0) tmp_result++;
            if (list[i].s <= 0) tmp_result++;
            result = max(result, tmp_result);
            dfs(d + 1);
            if (list[d].s <= 0) tmp_result--;
            if (list[i].s <= 0) tmp_result--;
            list[d].s += list[i].w;
            list[i].s += list[d].w;
        }
    }
}


int main() {
    freopen("input.txt", "r", stdin);
    input();
    dfs(0);
    cout << result << endl;
}