[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보다 작은 가장 큰 피보나치 수를 빼는 과정을 반복하는 것입니다.
아래는 위 과정을 정리한 소스코드입니다.
소스코드
지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.
'PS > 백준' 카테고리의 다른 글
[BOJ] 백준 9576번 : 책 나눠주기 (JAVA) (0) | 2020.10.23 |
---|---|
[BOJ] 백준 2862번 : 수학 게임 (JAVA) (0) | 2020.10.14 |
[BOJ] 백준 13034번 : 다각형 게임 (JAVA) (0) | 2020.10.12 |
[BOJ] 백준 11758번 : CCW (JAVA) (0) | 2020.10.09 |
[BOJ] 백준 5620번 : 가장 가까운 두 점의 거리 (JAVA) (0) | 2020.10.08 |
댓글