[BOJ] 백준 16896번 : 더일곱이 게임 (JAVA)

문제

구사과와 큐브러버가 더일곱이 게임을 하려고 한다. 더일곱이 게임은 정수 1이 적혀있는 종이를 이용해 게임을 진행하고, N을 만드는 사람이 게임을 지게 된다.

 

두 사람은 턴을 번갈아 가지며 게임을 하고, 각 사람은 자신의 턴이 왔을 때, 종이에 적힌 수에 1을 더하거나, 2를 곱해야 한다. 정수는 N보다 커지면 안 된다.

 

게임은 구사과가 먼저 시작한다.

 

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

 

 

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 10,000)이 주어진다. 둘째 줄부터 T개의 줄에 테스트 케이스의 정보가 한 줄에 하나씩 주어진다. 정보는 정수 N(2 ≤ N ≤ 10¹⁵)로 이루어져 있다.

 

 

출력

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

 

 

풀이

게임 이론을 이용하여 풀 수 있는 문제였습니다.

 

 

1부터 시작하여 종이에 적힌 수에 1을 더하거나 2를 곱하면서 N을 만드는 사람이 지는 규칙의 게임이었습니다.

 

N의 최댓값이 매우 큰 수이므로 규칙성을 찾아야하는데, N을 대충 200 정도로 잡고 dp를 짜서 koosaga가 이기는 경우를 찾으면 아래와 같은 수열이 나옵니다. koosaga가 이기는 경우로 찾은 이유는 koosaga가 대부분 지기 때문입니다.

 

 

"1, 3, 9, 11, 33, 35, 41, 43, 129, 131, 137, 139, 161, 163, 169, 171, ..."

 

 

이제, 위 수열을 oeis.org 사이트에 검색해 봅시다.

 

 

A145812 - OEIS

 

 

들어가 보시면, 우리가 위에서 구한 수열을 유도해 내는 과정이 상세히 나와 있습니다.

 

저는.. 그러한 공식들을 이해하려고 노력하였으나, 모르는 기호가 다수 보여서 포기하였고, 중간에 예제를 통하여 어떤 수 x가 수열 안에 들어가는지 여부에 대한 힌트를 얻을 수 있었습니다.

 

 

 

 

위 수식을 따라가보면, n이 주어졌을 때 n번째 수열의 요소는 무엇인지 구하는 방법과 M이 주어졌을 때 M이 몇 번째 수열의 속하는지 구하는 방법을 알 수 있습니다.

 

 

우리는 후자의 방법을 알아야 합니다.

 

위 식을 보면, M = 521이므로, 2 * (521 - 1) = 2¹⁰ + 2⁴ 와 같이 2의 거듭제곱의 덧셈으로 이루어진다는 것을 알 수 있습니다. 

 

그리고 x = 2⁴ + 2¹ + 1 = 19 라고 명시되어있는데, 아마도 제 생각에는 아래와 같은 수식이 성립하는 것 같습니다.

 

 

2 * (M - 1) = 2^p + 2^q + ... 일 때, x = 2^{(p_/2 - 1)} + 2^{(q_/2 - 1)} + 1.

그리고 p와 q는 짝수이어야 합니다. x는 수열의 인덱스이므로 자연수가 되어야하기 때문이죠.

 

 

따라서, 특정 M이 위 수열 안에 있을 조건은 아래와 같습니다.

 

 

1. M은 홀수이어야 한다.

2. 2 * (M - 1) 한 값은 2의 거듭제곱의 합으로 이루어지는데, 모든 2의 지수가 짝수이어야 한다.

 

 

이제, 직접 홀수인 M에 대하여 가장 큰 2의 제곱수만큼 빼 보면서 모든 지수가 짝수인지 확인하면 됩니다.

참고로, 2^x <= A에서 가장 큰 x를 구하기 위해서는 x = log₂A를 취한 값을 내림해야 합니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

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