[BOJ] 백준 2373번 : Fibonacci Game (JAVA)

문제

당신은 N(2≤N≤1,000,000)개의 구슬을 가지고 다음과 같은 게임을 하려고 한다. 게임은 두 사람이 번갈아 가면서 진행하며, 1번 사람이 몇 개의 구슬을 가져가는 것으로 게임이 시작된다.

 

1번 사람이 처음에 구슬을 가져갈 때는 몇 개라도 가져갈 수 있지만 N개의 구슬을 다 가져가서는 안 된다. 그 후에 구슬을 가져갈 때는, 상대편이 바로 전에 가져간 개수의 2배 이하를 가져갈 수 있다.

 

즉, 상대편이 1개를 가져갔다면, 당신은 1개, 또는 2개를 가져갈 수 있는 것이다. 이런 식으로 게임을 진행하여, 마지막으로 구슬을 가져간 사람이 이기게 된다.

 

예를 들어, N=3인 경우를 보자. 1번 사람이 몇 개를 가져가도 2번 사람이 남아있는 구슬을 다 가져갈 수 있다. 반면에 N=4인 경우에는, 1번 사람이 1개를 가져가면 이기게 된다.

 

1번 사람의 입장이 되어, 처음에 몇 개의 구슬을 가져갈 것인지를 결정하는 프로그램을 작성하시오. 만약 가능한 경우가 여러 가지 존재한다면, 더 적은 수의 구슬을 가져가는 것으로 한다. 만약 몇 개를 가져가도 지게 된다면, -1을 출력한다.

 

 

입력

첫째 줄에 정수 N이 주어진다.

 

 

출력

가져갈 구슬의 개수, 또는 -1을 출력한다.

 

 

풀이

약간의 정수론 지식과 게임 이론을 활용하여 풀 수 있는 문제였습니다.

 

 

일단, N을 100이하 정도로 잡고 메모이제이션으로 돌리면 N에 따른 ans가 어떻게 변화하는지 살펴봅시다.

 

 

 

 

일단, 정확한 규칙은 모르겠으나 N이 피보나치 수일 때는 선공이 무조건 필패하는 것처럼 보입니다.

 

그 외에는 1, 1 2, 1 2 3 1, 1 2 3 1 5 1 2, ... 로 수가 나열되는데 좀 더 이쁘게 보기 위해서 다르게 값을 출력해 보겠습니다.

 

 

 

 

이제, ans가 -1과 -1이 되는 사이의 수들을 살펴봅시다.

 

둘째 줄부터

 

 

1

 

1, 2

 

1, 2, 3, 1

 

1, 2, 3, 1, 5, 1, 2

 

...

 

 

로 나열되는 것을 알 수 있습니다.

 

즉, -1과 -1 사이에는 무슨 규칙인지는 모르겠으나, -1과 -1 사이에 있는 수의 개수에 따라 "1, 2, 3, 1, 5, 1, 2, ..." 라는 수열이 나열된다고 할 수 있습니다.

 

이제, 이 수열의 규칙성을 찾아야 하는데, 일단 위의 내용을 표로 표현해 보겠습니다.

 

 

idx	1	2	3	4	5	6	7
num	1	2	3	1	5	1	2

 

 

idx는 단순히 수의 순서를 넘버링 매긴 것이고, num은 수열의 수를 뜻합니다.

 

위의 표를 보면 알 수 있듯이, idx가 피보나치 수일 때는 num도 그대로 피보나치 수가 된다는 것을 알 수 있습니다.

 

또한, idx가 피보나치 수가 아닐 때는 idx에서 idx 이하의 피보나치 수 중 가장 큰 피보나치 수를 뺀 값과 같다는 것을 알 수 있습니다.

 

여기서 idx 에서 idx 이하의 피보나치 수 중 가장 큰 피보나치 수를 뺀다는 아이디어가 가장 중요합니다.

 

가령, N이 30이라고 하면, 30 이하의 가장 큰 피보나치 수는 21이므로 N이 9일 때 게임을 하는 것과 같게 됩니다.

 

다시, N이 9라면, 9 이하의 가장 큰 피보나치 수는 8이므로 N이 1일 때 게임을 하는 것과 같게 됩니다.

 

그래서 N이 30일 때는 구슬을 1개만 가져감으로써 게임에서 이길 수 있습니다.

 

 

따라서, 우리가 해야할 일은 2가지로 줄었습니다.

 

첫 번째는 N이 피보나치 수인지 확인하는 것입니다.

 

이 경우, 바로 ans = -1로 처리하면 됩니다.

 

두번째는 N이 피보나치 수가 아닐 경우, N이 피보나치 수가 될때까지 N보다 작은 가장 큰 피보나치 수를 빼는 과정을 반복하는 것입니다.

 

 

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

 

 

소스코드

 

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