BOJ 16987) 계란으로 계란치기 (C++)

16987번: 계란으로 계란치기

 백트래킹을 이용해 풀었다.

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

0번째 계란부터 시작해서 백트래킹으로 계란을 치는 경우의 수를 모두 탐색한다.

idx == N 인 경우 모든 계란들에 대해 과정을 끝냈으므로 탐색을 종료한다. 

cnt >= N-1이면 모든 계란이 깨졌거나 손에 든 계란을 제외한 모든 계란이 다 깨진 상태이므로 더 이상 깰 수 있는 계란이 없으므로 탐색을 종료한다. 

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define x first
#define y second

int N, ans;
vector<pii> v;  // {내구도, 무게}

void egg(int idx, int cnt){  
  if(idx==N||cnt==N-1){
    if(ans<cnt){
      ans=cnt;
    }
    return;
  } 
  if(v[idx].x<=0) {
    egg(idx+1, cnt);
  } else {
    for(int i=0;i<N;i++){
      if(i==idx) continue;
      if(v[i].x<=0) continue;
      v[i].x-=v[idx].y;
      v[idx].x-=v[i].y;
      if(v[i].x<=0&&v[idx].x<=0) egg(idx+1, cnt+2);
      else if(v[i].x<=0||v[idx].x<=0) egg(idx+1, cnt+1);
      else egg(idx+1, cnt);
      v[i].x+=v[idx].y;
      v[idx].x+=v[i].y;
    }
  }
}

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

  cin>>N;
  v.resize(N);
  for(int i=0;i<N;i++){
    cin>>v[i].x>>v[i].y;
  }
  egg(0,0);
  cout<<ans;

  return 0;
}