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

www.acmicpc.net/problem/16987

16987번: 계란으로 계란치기

 

n의 범위가 1부터 8까지이기 때문에 브루트 포스 & 백트래킹을 하면 풀리는 문제이다.

주의할 점: hand== n인 기저조건까지 도달하기 위해 모든 조건에서 backtracking함수를 실행시켜야 한다는 것이다. '

 

++괜히 경우의 수를 출력한다고 했다가 너무 많은 경우의 수라서 무한 루프 도는 것처럼 보였다...

 

#include <stdio.h>
#include <algorithm>
#define MAX 8

//n=8이기 때문에 다 해보기

using namespace std;

int n, result = 0;
int eggs[MAX][2];

void BackTracking(int hand, int broke)
{

  if (hand == n)
  {
    result = max(result, broke);
    return;
  }

  if (eggs[hand][0] <= 0)
  {
    BackTracking(hand + 1, broke);
    return;
  }

  bool flag = true;
  for (int i = 0; i < n; i++)
  {
    if (i == hand || eggs[i][0] <= 0)
      continue;

    int tmp = 0;
    eggs[hand][0] -= eggs[i][1];
    if (eggs[hand][0] <= 0)
    {
      tmp++;
    }
    eggs[i][0] -= eggs[hand][1];
    if (eggs[i][0] <= 0)
    {
      tmp++;
    }

    flag = false;
    BackTracking(hand + 1, broke + tmp);
    eggs[hand][0] += eggs[i][1];
    eggs[i][0] += eggs[hand][1];
  }

  if (flag)
    BackTracking(hand + 1, broke);
}

int main(void)
{
  scanf("%d", &n);

  for (int i = 0; i < n; i++)
  {
    scanf("%d%d", &eggs[i][0], &eggs[i][1]);
  }

  BackTracking(0, 0);

  printf("%d\n", result);
  return 0;
}