[백준 16987] 계란으로 계란치기 (C#, C++) - soo:bak

문제 링크

16987번 - 계란으로 계란치기

설명

계란을 왼쪽부터 순서대로 집어 들어 다른 계란을 한 번씩 쳐서 최대한 많은 계란을 깨는 문제입니다.

접근법

왼쪽부터 계란을 하나씩 집어 듭니다. 손에 든 계란이 이미 깨졌거나 칠 수 있는 다른 계란이 없으면 아무 행동 없이 다음 계란으로 넘어갑니다.

손에 든 계란이 멀쩡하고 칠 수 있는 계란이 있다면, 깨지지 않은 다른 계란 중 하나를 골라 칩니다. 두 계란은 서로 상대방의 무게만큼 내구도가 감소하고, 내구도가 0 이하가 되면 깨집니다.

어떤 계란을 칠지에 따라 결과가 달라지므로, 모든 경우를 시도해봅니다. 한 계란을 친 후 다음 계란으로 넘어가 재귀적으로 탐색하고, 돌아올 때 내구도를 원래대로 복구합니다.

모든 계란을 다 집어본 후 깨진 계란의 수를 세어 최댓값을 갱신합니다. 계란이 최대 8개이므로 모든 경우를 탐색해도 시간 내에 해결할 수 있습니다.

---

Code

C#

using System;

class Program {
  static int N, best;
  static int[] dur = new int[8], wt = new int[8];

  static void Dfs(int idx) {
    if (idx == N) {
      var broken = 0;
      for (var i = 0; i < N; i++) if (dur[i] <= 0) broken++;
      if (broken > best) best = broken;
      return;
    }

    if (dur[idx] <= 0) {
      Dfs(idx + 1);
      return;
    }

    var hit = false;
    for (var j = 0; j < N; j++) {
      if (j == idx || dur[j] <= 0) continue;
      hit = true;
      dur[idx] -= wt[j];
      dur[j] -= wt[idx];
      Dfs(idx + 1);
      dur[j] += wt[idx];
      dur[idx] += wt[j];
    }

    if (!hit) Dfs(N);
  }

  static void Main() {
    N = int.Parse(Console.ReadLine()!);
    for (var i = 0; i < N; i++) {
      var parts = Console.ReadLine()!.Split();
      dur[i] = int.Parse(parts[0]);
      wt[i] = int.Parse(parts[1]);
    }

    Dfs(0);
    Console.WriteLine(best);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int N, bestAns;
int dur[8], wt[8];

void dfs(int idx) {
  if (idx == N) {
    int broken = 0;
    for (int i = 0; i < N; i++) if (dur[i] <= 0) broken++;
    bestAns = max(bestAns, broken);
    return;
  }

  if (dur[idx] <= 0) {
    dfs(idx + 1);
    return;
  }

  bool hit = false;
  for (int j = 0; j < N; j++) {
    if (j == idx || dur[j] <= 0) continue;
    hit = true;
    dur[idx] -= wt[j];
    dur[j] -= wt[idx];
    dfs(idx + 1);
    dur[j] += wt[idx];
    dur[idx] += wt[j];
  }
  if (!hit) dfs(N);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> N;
  for (int i = 0; i < N; i++) cin >> dur[i] >> wt[i];

  dfs(0);
  cout << bestAns << "\n";

  return 0;
}