[BOJ / C++] 16987 계란으로 계란치기

https://www.acmicpc.net/problem/16987

기본적인 dfs문제에 조건이 조금 들어있는 문젠데 어이없게 헤맸다.

1. 계란을 칠 때 계란 벡터 내 값 자체를 안바꿔주고, 다른 변수에 넣어두고 변수값을 바꿔줬다.
2. dfs 호출 후 다시 값을 안 돌려놓음 😀

문제풀이

1. dfs 함수 (hitEgg) 인자로 계란의 start 인덱스를 받는다. 가장 오른쪽에 위치한 계란일 경우 종료한다.
2. 현재 계란이 깨져있는 경우 바로 다음 인덱스로 재귀호출
3. 모든 계란을 보면서 자기자신이거나 깨진 경우에 넘어가고, 아닌 경우 계란 친 후 다음 인덱스로 재귀호출!
   백트래킹 후에는 다시 원래 깨기 전으로 돌려줘야 함!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector <pair<int,int>> eggs; //내구도, 무게
int maxCnt=-1; //최대 몇 개의 계란을 깨냐

void hitEgg(int start){
    if(start==N){  //가장 오른쪽에 위치한 계란일 경우 종료
        int cnt=0;
        for(auto & egg : eggs){
            if(egg.first<=0) cnt++;
        }
        maxCnt=max(maxCnt,cnt);
        return ;
    }

    // 손에 든 계란이 깨져있는 경우
    if(eggs[start].first<=0) {
        //다음으로 넘어감
        hitEgg(start+1);
        return;
    }

    bool isExist=false; //안깨진 계란이 있는지
    // 깨지지 않은 다른 계란 중에서 하나를 친다.
    for(int i=0;i<N;i++){
        if(start==i) continue; //자기 자신
        if(eggs[i].first<=0) continue; //깨진 계란일 경우 그냥 넘어감.

        isExist=true;

        //계란 치기
        eggs[start].first-=eggs[i].second;
        eggs[i].first-=eggs[start].second;
        hitEgg(start+1);
        eggs[start].first+=eggs[i].second;
        eggs[i].first+=eggs[start].second;
    }

    //남은 것중 안깨진 게 없을 경우 더 볼 것 없이 바로.
    if(!isExist) hitEgg(N);
}

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

    hitEgg(0); //0번 계란부터 친다.
    cout<<maxCnt<<"\n";

}