[BOJ] 백준 16876번 : 재미있는 숫자 게임 (JAVA)

문제

구사과와 큐브러버는 "숫자 게임"을 하려고 한다. 게임은 다음과 같은 방식으로 진행해야 한다.

 

 

1. 4자리 정수 N과 턴의 수 M을 정한다.
2. 게임은 구사과가 먼저 시작하며, 턴을 번갈아가면서 진행해야 한다.
3. 각 사람은 자신의 턴이 되었을 때, 정수의 숫자 하나를 골라 1 증가시켜야 한다. 고른 숫자가 9인 경우에는 0이 된다.

 

 

예를 들어, 3590은 4590, 3690, 3500, 3591 중 하나로 변경시킬 수 있다. 게임이 종료된 후에 정수가 N보다 커진 경우에는 구사과가 게임을 이기고, 그 외의 경우에는 큐브러버가 게임을 이긴다. 두 사람은 최적의 방법으로 게임을 한다.

 

N과 M이 주어졌을 때, 누가 이기는지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 4자리 정수 N과 M이 주어진다.

 

 

출력

구사과가 이기는 경우에는 "koosaga", 큐브러버가 이기는 경우에는 "cubelover"를 출력한다.

 

 

제한

- 0 ≤ N < 10⁴

- 0 ≤ M ≤ 100

 

 

풀이

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

 

 

특정 N의 자리 수의 +1을 취해가면서 p턴이 지났을 때, 원래 있던 수가 현재 수보다 크면 선공이 이기고, 나머지 상황에는 후공이 이기는 것이 게임의 규칙이었습니다.

 

 

문제를 푸는 방식 자체는 간단합니다.

 

 

dp[i][j] = x : j턴이고 i수일 때, x가 0이면 패배하고, x가 1이면 승리함.

 

 

위와 같이 점화식을 정의한 후, 메모이제이션을 이용하여 각 자리수의 +1을 취하여 p턴이 M턴이 될 때까지 반복합니다.

이 p턴이 M턴과 같아지는 순간이 바로 기저 사례이고, 이 기저 사례를 잘 정의하는 것이 중요했습니다.

또한, 선공과 후공의 승리조건이 다르다는 점에 유의해야합니다.

 

 

각 플레이어의 승패 조건을 알기 위해서 케이스를 분류해 보겠습니다.

 

 

(1) M이 짝수인 경우

선공은 0턴부터 시작하므로 M이 짝수라는 의미는 마지막 턴은 선공 차례라는 뜻입니다.

만약, M턴에서 선공이 이길 수 있는 조건이 있다면, (M - 1)턴에서 후공은 패배하고, M턴에서 선공이 모두 패배한다면, (M - 1)턴에서 후공은 승리할 것입니다.

 

 

(2) M이 홀수인 경우

선공은 0턴부터 시작하므로 M이 홀수라는 의미는 마지막 턴은 후공 차례라는 뜻입니다.

만약, M턴에서 후공이 이길 수 있는 조건이 있다면, (M - 1)턴에서 선공은 패배하고, M턴에서 후공이 모두 패배한다면, (M - 1)턴에서 선공은 승리할 것입니다.

 

 

따라서, 위 2가지 케이스에 의하여 기저 사례를 M의 홀짝성에 따라 정의할 수 있습니다.

 

 

이제, 우리가 할 일은 단순해졌습니다.

 

메모이제이션을 통하여, i 턴의 각 자리의 수를 +1한 값을 차례 차례 넘긴 후, 4가지 케이스에 대해서 하나라도 (i + 1) 턴의 상대방이 패배하는 경우가 있으면, i 턴의 플레이어는 승리하고, 반대로,(i + 1) 턴의 상대방이 모두 승리한다면, i 턴의 플레이어는 패배하는 코드를 짜시면 됩니다.

 

 

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

 

 

소스코드

 

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