[BOJ] 백준 16894번 : 약수 게임 (JAVA)

문제

구사과와 큐브러버는 약수 게임을 하려고 한다. 약수 게임은 종이에 정수를 적으면서 진행하고, 두 사람은 턴을 번갈아 가진다.

 

가장 처음에 종이에는 정수 N이 적혀있다. 각자의 턴이 돌아올 때마다, 종이에 적힌 수를 지우고, 그 수의 약수를 다시 적는다. 이 때, 약수는 1과 자기자신이 아닌 수가 되어야 한다. 더 이상 적을 수가 없는 사람이 게임을 이긴다.

 

두 사람이 최적의 방법으로 게임을 했을 때, 누가 이기는지 구하는 프로그램을 작성하시오. 게임은 구사과가 먼저 시작한다.

 

 

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1013)이 주어진다.

 

 

출력

구사과가 이기는 경우에는 "koosaga"를, 큐브러버가 이기는 경우에는 "cubelover"를 출력한다.

 

 

풀이

약수와 게임 이론을 이용한 문제였습니다.

 

 

특정 수를 지우고 그 수의 약수를 쓰는 행위를 반복하면서 더 이상 수를 쓸 수 없는 사람이 이기는 것이 게임의 규칙이었습니다. 여기서, 1과 자기 자신은 다시 쓸 수 없습니다.

 

 

선공과 후공이 이기는 조건을 알기 위해서 특정 수 N을 케이스에 따라 나눠 보겠습니다.

 

 

(1) N이 소수

N이 소수일 때는 약수를 더 이상 쓸 수 없으므로 선공이 승리합니다.

 

 

(2) N이 합성수

N이 합성수일 때는 선공이 이길 수도 있고, 후공이 이길 수도 있습니다.

 

가령, 8일 때는 선공이 8 -> 4 -> 2 로 전개하여 이길 수 있지만, 6일 때는 선공이 6 -> 3 로 전개하여 패배합니다.

저는 선공이 소수일 때는 무조건 이기고 합성수일 때는 이기는 경우도 존재한다는 것에 초점을 맞춰서 후공이 이기는 경우를 알아 보았습니다.

 

 

 

그리고 후공이 승리하는 조건은 단 하나 밖에 없다는 것을 알게 되었습니다. 바로, N = pq(p, q는 소수) 일 때입니다.

만약, N = pq 꼴이라면, 선공은 반드시 후공에게 소수인 약수를 넘겨줄 수 밖에 없기 때문에 후공이 필승하게 됩니다.

 

 

이제, 우리는 N이 pq꼴인지 검사하는 로직만 짜면 됩니다.

(참고로, N = pq인 N을 semi-prime 이라고 부릅니다.)

 

 

전반적인 로직은 아래와 같습니다.

 

 

1. 2 <= a <= sqrt(N)인 a로 N을 하나씩 나누어 본다.

 

2. 만약, a로 나누어 떨어진다면, 더 이상 나누어 떨어지지 않을 때까지 a로 나누어 본다.

 

3. 1~2번 과정을 수행하면서 a로 나눈 횟수가 3번 이상이면 그 수는 semi-prime이 아니다.

 

4-1. a로 나눈 횟수가 2번이면, 그 수는 N = q*q 꼴이므로 semi-prime이다.

 

4-2. a로 나눈 횟수가 1번이면, 그 수는 N = q * (N / q) 꼴이므로 semi-prime 이다.

 

 

아래 주석이 달린 코드를 함께 읽어보시면 위 로직이 어떻게 돌아가는지 이해하실 수 있을 겁니다.

 

 

소스코드

 

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