[BOJ] 백준 16888번 : 루트 게임 (JAVA)

문제

구사과와 큐브러버가 루트 게임을 하려고 한다. 루트 게임은 정수 하나를 이용하고, 가장 처음에 이 정수는 N이다.

 

두 사람은 턴을 번갈아 가지면서 게임을 하고, 구사과가 먼저 게임을 시작한다. 각 턴에서 각 사람은 1보다 크거나 같은 완전제곱수 x를 하나 고르고, N에서 x를 뺀다. 정수는 0보다 작아질 수 없으며, 0을 만드는 사람이 게임을 이긴다.

 

두 사람이 모두 최적의 방법으로 게임을 했을 때, 이기는 사람이 누구인지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 105)가 주어진다. 둘째 줄부터 T개의 줄에 테스트 케이스가 한 줄에 하나씩 주어지며, N(1 ≤ N ≤ 106)이 주어진다.

 

 

출력

각각의 테스트 케이스마다 이기는 사람을 출력한다. 구사과가 이기는 경우에는 "koosaga", 큐브러버가 이기는 경우에는 "cubelover"를 출력한다.

 

 

풀이

다이나믹 프로그래밍과 게임 이론을 활용하여 풀 수 있는 문제였습니다.

 

이 문제를 풀기 위해서 중요한 요소는 바로 '패배 조건'과 '필승 조건'입니다.

 

 

만약 N = 2 일 때, 선공이 패배를 한다고 해 봅시다. 그렇다면. N = i (i >= 3)인 순간에서 N = 2로 만드는 모든 경우는 선공이 승리한다고 해석할 수 있습니다. 선공이 N = i에서 N = 2로 만들어 버리는 순간 후공은 패배하기 때문이죠.

 

 

반대로, N = i ^ 2일 경우, 문제의 조건에 따라서 선공이 무조건 이깁니다.

N이 제곱수 일 경우, 그 제곱수만큼 수를 다 빼면 되기 때문이죠.

 

 

위의 두 가지 조건을 인지하였다면, 코드를 짜는 것은 간단합니다.

먼저, 필승 조건이 되는 경우를 arr[i] = true로 처리해 줍니다.

 

그리고, 초기 조건으로 arr[2] = false로 설정해 줍니다. 선공이 1을 빼고, 후공이 1을 빼면, 선공이 패배하기 때문입니다.

이후, arr[i]가 false인 순간을 포착한 후, arr[i + j * j] = true로 처리해 줍니다.

 

10^6까지 arr의 승패 처리를 모두 하였다면, 이제 문제의 입력을 받고 출력만 하면 됩니다.

아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드

 

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