JArchive 프로그래밍 일기

문제

계란으로 계란치기 백준 16987

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
// 16987 계란으로 계란치기

int n, a, b, answer;
vector<pair<int, int>> v;

void dfs(int depth){ // depth == 집어든 계란의 인덱스.

  if(depth == n){
    int crashcnt = 0;
    for(int i = 0; i < n; i++){
      if(v[i].X <= 0) crashcnt++;
    }
    answer = max(answer, crashcnt);
    return;
  }

  // 현재 집어든 계란이 깨졌으면, 그 옆에 다른 계란을 집어든다.
  if(v[depth].X <= 0) dfs(depth+1);
  else {
    bool crashflag = false;
    for (int i = 0; i < n; i++) {
      // i가 현재 집은 계란이거나 이미 깨졌으면 지나감
      if (i == depth || v[i].X <= 0) continue;

      v[i].X -= v[depth].Y;
      v[depth].X -= v[i].Y;

      crashflag = true; // 계란 깼음
      dfs(depth + 1); // 다음 계란을 집는다.

      v[i].X += v[depth].Y;
      v[depth].X += v[i].Y;
    }
    if (!crashflag) dfs(n); // 더이상 깰 계란이 없으면? 개수를 센다.
  }
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i <n; i++){
    cin >> a >> b;
    v.push_back({a,b});
  }

  dfs(0); // 가장 왼쪽(0번째) 계란부터 시작한다.
  cout << answer;
  return 0;
}

리뷰

다시 풀어봐야 할 문제.
백트래킹 카테고리에 있었는데. 문제를 이해 못해서 헤맸다.

집어든 계란을 depth라고 두고, 집어든 계란으로 가능한 많은 계란을 깨면 된다. (공격하면 된다.)
만약 공격할 계란이 남아있지 않거나 내가 집어든 계란이 깨진다면, 집어든 계란을 바꾼다.
집어든 계란을 바꾼다는 의미가 depth를 +1 한다는 의미다.

내가 집어든 계란과 그 계란으로 깰(공격할)계란들이 헷갈려서 갈피를 못잡았다.