문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오. baekjoon

코드

#include <iostream>

using namespace std;

int checked[1501][1501];

int go(int a, int b, int c) {
  checked[a][b] = true;
  if (a == b && b == c) return 1;

  int x, y;
  // a, b
  x = min(a, b);
  bool is_left_min = (x == a);
  y = max(a, b);
  int result1 = 0;
  if (is_left_min) {
    if (!checked[2 * a][b - a]) result1 = go(2 * a, b - a, c);
  } else {
    if (!checked[a - b][2 * b]) result1 = go(a - b, 2 * b, c);
  }

  // a, c
  x = min(a, c);
  is_left_min = (x == a);
  y = max(a, c);
  int result2 = 0;
  if (is_left_min) {
    if (!checked[2 * a][b]) result2 = go(2 * a, b, c - a);
  } else {
    if (!checked[a - c][b]) result2 = go(a - c, b, 2 * c);
  }

  // b, c
  x = min(b, c);
  is_left_min = (x == b);
  y = max(b, c);
  int result3 = 0;
  if (is_left_min) {
    if (!checked[a][2 * b]) result3 = go(a, 2 * b, c - b);
  } else {
    if (!checked[a][b - c]) result3 = go(a, b - c, 2 * c);
  }

  if (result1 || result2 || result3) return 1;
  
  return 0;
}

int main() {
  int a, b, c;
  cin >> a >> b >> c;

  cout << go(a, b, c);
}

풀이

(a, b), (a, c), (b, c) 에 대해서 모두 x와 y를 결정해서 a == b == c 인지 확인하는 방식이다. 그냥 이대로만 하면 (a, b)를 선택하는 경우에 걸려 반복되게 된다. 따라서 이미 체크했던 a, b, c에 대해서는 다시 체크하지 않아야 하는 조건이 필요한데, checked 배열을 통해 체크하고 있다. 3차원 배열로 만들 경우 1500^3만큼 메모리를 할당할 수 없기에, a + b + c의 개수는 변하지 않는다는 점을 이용해서 a와 b에 대해서만 관리하여 2차원으로 만들 수 있다.