[BOJ] 백준 19253번 : Don't Split The Atom! (JAVA)

문제

Two mad (and evil) scientists, Professor Zoom and Doctor Horrible, have just obtained n atoms of a very rare element, which they want to share between themselves. They have decided to play the following game:

 

First, Professor divides the atoms into two non-empty groups. Next, Doctor takes one group and uses it for his evil purposes, and splits the other into two non-empty parts. Then, Professor takes one of the parts, and divides the other one again into two, returning it to Doctor.

 

The game goes on -- with every turn, a scientist taking one of the parts, and splitting the other -- until one of the players is forced to split a single atom. This results in an explosion, and the unlucky splitter loses the game (probably with his life).

 

Knowing the number of atoms n determine which one of the villains survives the game.

 

 

 

 

입력

The first line of input contains the number of test cases z (1≤z≤50). The descriptions of the test cases follow.

Every test case consists of one integer n (1≤n≤1000000) -- the initial number of atoms.

 

 

출력

For each test case output a line containing a single character: 'A' if Professor wins the game, 'B' if Doctor wins.

 

 

풀이

간단한 게임 이론 문제였습니다.

 

 

Professer와 Doctor가 게임을 하는데, Professer가 분자 하나를 두 그룹으로 쪼개면, Doctor는 한 그룹을 택해서 다시 두 그룹으로 쪼갭니다. 이 게임을 반복하면서, 둘 중 한 명이 더 이상 분자를 쪼갤 수 없게 되면 패배하는 규칙이었습니다.

 

여기서, 분자를 분리하지 못한다는 것은 수가 1이 되는 것을 의미합니다.

 

 

N을 1부터 찬찬히 나열해 봅시다.

N = 1일 때는 Professer가 쪼갤 수 없으므로 패배합니다.

 

N = 2일 때는 Professer가 (1, 1)으로 그룹을 나누면, Doctor가 어떤 그룹을 고르더라도 분자를 쪼갤 수 없으므로 Professer가 승리합니다.

 

N = 3일 때는 Professer가 (1, 2)으로 그룹을 나누면, Doctor가 2를 고를 것이고, 2로 (1, 1)으로 그룹으로 나누게 되어 Professer가 패배합니다.

 

N = 4일 때는 Professer가 (2, 2)으로 그룹을 나누면, N = 3에서 본 것과 같이 패배하므로 (1, 3)으로 나눕니다.

이 때, Doctor는 1은 고를 수 없고, 3을 골라도 패배합니다. 따라서, Professer가 승리합니다.

 

 

이와 같이 N을 나열하다보면, N이 홀수일 때는 Professer가 승리하고, N이 짝수일 때는 Doctor이 승리함을 알 수 있습니다.  

 

 

이제 게임의 승패 조건을 알게 되었으므로 코드로 작성하시면 됩니다.

아래를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.