[BOJ] 백준 2862번 : 수학 게임 (JAVA)

문제

상덕이와 희원이는 동전 게임을 하면서 시간을 보낸다. 동전 게임은 동전 N개를 가지고 하는 게임이고, 규칙은 다음과 같다.

 

상덕이가 먼저 게임을 하고, 그 다음엔 희원이, 그 다음에 상덕이, 희원이 순서대로 게임을 한다. 순서대로 첫 번째 턴, 두 번째 턴, 세 번째 턴, ...

 

상덕이는 첫 번째 턴에서 가져갈 수 있는 동전의 개수는 1보다 크거나 같고, N보다 작거나 같다.

 

그 다음 턴부터는 동전을 이전 턴에서 그 사람이 가져간 동전 개수의 최대 2배만큼 가져갈 수 있다. (동전을 적어도 1개는 가져가야 한다)

 

이렇게 플레이를 하다가 마지막 동전을 가져가는 사람이 이긴다.

 

상덕이와 희원이가 항상 최적의 방법으로 게임을 한다. 이 말은 어떤 상황에서 플레이어 A가 B를 항상 이길 수 있다면, A가 항상 이긴다는 것이다.)

 

이때, 상덕이가 이기기 위해서는 첫 번째 턴에서 동전을 몇 개 가져가야 하는지를 구하는 프로그램을 작성하면 된다. 이러한 동전의 개수가 여러 개 나올 수 있는데, 그 때는 가장 적은 개수를 출력하면 된다.

 

 

입력

첫째 줄에 동전의 개수 N이 주어진다. (2 ≤ N ≤ 10¹⁵)

 

 

출력

첫째 줄에 상덕이가 이기기 위해서 가져가야 하는 동전 개수의 최솟값을 출력한다.

 

 

풀이

약간의 정수론 지식과 게임 이론을 활용하여 풀 수 있는 문제이며, "2373번 Fibonacci Game" 문제와 상당히 유사했습니다.

 

 

N이 2일 때부터 동전을 몇 개 가져가야하는지 메모이제이션을 통해 구하고, 나열해 보면

 

 

1, 2, 3, 1, 5, 1, 2, 8, 1, 2, 3, 1, ... 

 

 

과 같은 수열이 나옵니다.

 

위의 수열은 "2373번 Fibonacci Game" 문제에서 다룬 것과 완전히 일치하므로 이 문제를 처음 접하신 분은 아래 포스팅을 먼저 읽어주시길 바랍니다.

 

 

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

 

 

이 문제는 N이 피보나치 수일 경우 그대로 N을 출력하고, 피보나치 수가 아닐 경우 N이 피보나치 수가 될때까지 N보다 작은 가장 큰 피보나치 수를 빼는 과정을 반복하면 됩니다.

 

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

 

 

소스코드

 

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