[백준 16987번] 계란으로 계란치기

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

16987번: 계란으로 계란치기

<문제 풀이>

1. 가장 왼쪽의 계란을 든다.
2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.

문제 조건을 그대로 dfs로 구현하면 된다.

<C++ 소스 코드> 백트랙킹

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
#define S first
#define W second
 
int n;
vector<pair<int, int> > egg;
int res = 0;
void dfs(int idx) { //idx번째 계란을 든다
    if (idx >= n) { //가장 최근에 든 계란이 가장 오른쪽에 위치한 경우
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (egg[i].S <= 0) cnt++; //깨진 계란 카운트
        }
        res = max(res, cnt);
        return;
    }
    bool flag = false; //idx번째 계란으로 다른 계란을 쳤는지 여부
    for (int i = 0; i < n; i++) {
        if (i == idx) continue; // 자기 자신 무시
        if (egg[idx].S > 0 && egg[i].S > 0) { // 계란을 칠 수 있으면
            egg[idx].S -= egg[i].W;
            egg[i].S -= egg[idx].W;
            flag = true;
            dfs(idx + 1);
            egg[idx].S += egg[i].W;
            egg[i].S += egg[idx].W;
        }
    }
    if(!flag) dfs(idx + 1); //계란을 칠 수 없으면 넘어간다.
 
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int s, w;
        cin >> s >> w;
        egg.push_back({ s,w });
    }
    dfs(0);
    cout << res;
    return 0;
}