[BOJ] 백준 1519번 : 부분 문자열 뽑기 게임 (JAVA)

문제

게임 판에 어떤 자연수 N이 쓰여 있을 때, 두 명의 플레이어가 턴을 번갈아가면서 이 게임을 하려고 한다.

 

매 턴이 돌아올때마다, 플레이어는 현재 게임 판에 쓰여 있는 수의 진 부분 문자열을 고를 수 있다. 그리고 나서 원래 수에서 뽑은 수를 뺀다. 진 부분 문자열이란 자기 자신을 제외한 모든 연속된 부분 문자열을 말한다.

 

예를 들어, 현재 게임 판에 2309가 써있을 때, 플레이어는 2, 3, 9, 23, 30, 230, 309를 고를 수 있다. 2를 고르면, 현재 게임 판에 쓰여 있는 수는 2307이 되고, 3은 2306, ..............., 309는 2000이 된다.

 

만약에 플레이어가 부분 문자열을 고를 수 없게되면, 게임에서 지게된다.

 

입력으로 현재 게임 판에 쓰여 있는 수 N이 주어졌을 때, 플레이어 1(첫 턴을 가지는 플레이어)이 이기기 위해서 골라야 하는 수를 출력하는 프로그램을 작성하시오. 만약 여러 가지 경우가 있다면, 가장 작은 것을 출력하고, 이길 수 없다면 -1을 출력한다.

 

 

입력

첫째 줄에 N이 주어진다. N은 1000000보다 작거나 같은 자연수이다.

 

 

출력

정답을 출력한다.

 

 

풀이

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

 

 

특정 문자열의 0으로 시작하지 않는 진 부분 문자열 집합을 구하고, 문자열에서 집합 내의 원소를 빼면서 더 이상 진 부분 문자열을 뽑을 수 없게 되는 사람이 패배하는 규칙의 게임이었습니다.

 

 

게임 이론을 풀 때는 현재 상황과 다음 상황을 정의하는 것이 중요한데, 다음 상황이 될 수 있는 여러 상황 중에 패배하는 경우가 단 하나라도 있다면, 현재 상황은 승리합니다.

 

 

위 내용을 잘 숙지하면서 문제를 풀어봅시다.

일단, dp 배열을 정의합니다.

 

 

dp[i] = x 에서 i 문자열에 대하여, x가 0일 때는 선공이 패배한다는 의미고, 0이 아닐 때는 선공이 승리한다는 의미입니다. 이 때, x != 0인 경우, x는 최소로 뺀 값을 뜻합니다.

 

 

N이 일의 자리 수일 경우에는 진 부분 문자열을 뽑을 수 없으므로 dp[1] = ... = dp[9] = 0 입니다.

N이 10일 때는 진 부분 문자열은 1입니다. 따라서 다음 상황은 9 밖에 없고, dp[9] = 0이므로 dp[10] = 1 로 정의할 수 있습니다. 다음 상황이 패배하는 상황이므로 현재 상황은 승리하기 때문이죠.

 

 

위와 같이 특정 문자열의 진 부분 문자열을 적당한 반복문으로 구현하여 Set에 넣고, 하나씩 빼 보면서 다음 상황 중 패배하는 상황들을 찾은 후, 최소의 값을 찾으면 됩니다.

 

 

진 부분 문자열을 구하는 부분은 아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드

 

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