[BOJ] 백준 12107번 : 약수 지우기 게임 1 (JAVA)

문제

A와 B가 약수 지우기 게임을 한다. 약수 지우기 게임은 두 사람이 즐기는 게임이다.

 

칠판에 1부터 N까지의 자연수가 적혀 있다. 각 사람은 자신의 턴에 칠판에 적힌 자연수 하나를 지우고, 그 자연수의 약수 중 칠판에 남아 있는 수들을 모두 지운다. 예를 들어, 칠판에 2,3,4,5,6이 적혀 있을 때, 6을 지우면, 그 약수인 2와 3 역시 지워야 한다. 자신의 턴에 숫자를 지우지 않을 수는 없다. 마지막 숫자를 지우는 사람이 지게 된다.

 

A와 B가 최적의 방법으로 게임을 할 때, 이기는 사람을 출력한다. 게임은 A가 먼저 시작한다.

 

 

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

 

 

출력

첫째 줄에 A가 이기는 경우 A, B가 이기는 경우 B를 출력한다.

 

 

풀이

게임 이론 문제였습니다.

 

일단, 규칙성이 바로 보이지 않으므로 N = 1 부터 쭉 나열해 봅시다.

 

 

N = 1일 때는 A가 1을 지워야하므로 무조건 B가 승리합니다.

 

N = 2일 때는 A가 1을 지워야 이길 수 있습니다.

 

N = 3일 때는 3을 지워야 이길 수 있습니다.

 

N = 4일 때는 4를 지워야 이길 수 있습니다.

 

N = 5 일 때는 1보다 큰 자연수를 지우는 것이 아니라, 1만 지워야 이길 수 있습니다.

가령, A가 1을 지우면 2, 3, 4, 5 중 B가 특정 수를 지우는데, 이 중 B가 어떤 것을 지워도 A가 이길 수 있다는 사실을 알 수 있습니다.

 

 

N을 5까지 나열해 보았을 때, '1'이라는 숫자가 이 게임에서 꽤 중요한 역할을 한다는 것을 알 수 있었습니다.

1보다 큰 자연수를 지웠을 때는 항상 1을 지우게 되지만, 1보다 작은 약수는 없으므로 1은 단순히 1만 지우게 됩니다.

 

따라서, 게임에서 1은 없는 수라고 가정한 뒤, 나머지 수를 가지고 게임해 보면서 A가 지는 상황이라면, 처음에 1을 지움으로써 승리할 수 있습니다.

 

 

위에서 언급한 1을 없다고 가정하면, 2, 3, 4, ... i를 이용하여 게임을 진행할 것입니다.

여기서, 2, 3, 4, ..., i 게임에서 A가 승리하면 결과적으로 A가 승리하는 것이고, A가 패배하면 2, 3, 4, ..., i가 아닌 1을 지움으로써 승리할 수 있게 됩니다.

 

결과적으로, N = 1일 때만 B가 이기고, 그 외에는 전부 A가 이긴다는 사실을 알 수 있습니다.

 

 

위에 내용을 토대로 간단하 코드를 작성하시면 됩니다.

 

 

소스코드

 

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