피씨방에서 피씨방비 내기 스타를 하다가 자원을 다 쓰고 유닛도 모두 전멸하는 어이없는 경우가 발생하여 무승부를 기록한 철기와 태현이는 다음과 같은 게임을 통해서 피씨방비를 내는 사람을 결정하고자 한다.

우선 2개의 숫자를 준비하고, 철기가 먼저 시작을 하게 된다.

두개의 숫자를 a 와 b라고 하자. a, b 중에 작은 숫자에서 1이상을 곱해서 만들어진 숫자를 다른 숫자에 빼서 다른 숫자로 바꾸게 된다. 여기서 다른 숫자가 0 보다 작아지게는 할 수 없다.

0 을 만들지 못했을 경우 다음은 태현이가, 그 다음은 철기가, 돌아가면서 게임을 하다가 둘 중에 작은 숫자가 0 이 되게 만들게 되면 게임에서 이기고 피씨방비를 낼 필요가 없어진다.

아래는 25와 7을 가지고 게임을 하는 예이다.

(시작) 25 7 -> (철기) 11 7 -> (태현) 4 7 -> (철기) 4 3 -> (태현) 1 3 -> (철기) 1 0 이러한 경우는 철기가 승리하게 된다.

임의의 자연수 a, b가 주어지고 태현이와 철기가 최선을 다해서 게임을 한다고 했을 때, 승자가 누구인지 출력하는 프로그램을 작성한다.

앞서 이야기 했듯이, 게임은 철기가 먼저 시작한다.

유클리드의 게임 timer 1s memory 64MB

유클리드의 게임 1s 64MB