[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에 넣고, 하나씩 빼 보면서 다음 상황 중 패배하는 상황들을 찾은 후, 최소의 값을 찾으면 됩니다.

 

 

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

 

 

소스코드

	import java.io.BufferedReader;
	import java.io.BufferedWriter;
	import java.io.InputStreamReader;
	import java.io.OutputStreamWriter;
	import java.util.HashSet;
	import java.util.Iterator;
	import java.util.Set;
	public class Main {
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	int N = Integer.parseInt(br.readLine());
	if (N < 10) {
	bw.write("-1");
	} else {
	// 0이면 패배, 0이 아니면 승리.
	// 승리일 경우, 가장 최소로 뺀 값을 저장.
	int[] dp = new int[N + 1];
	for (int n = 10; n <= N; n++) {
	String str = String.valueOf(n);
	Set<String> set = new HashSet<>(); // 진 부분 문자열 집합.
	for (int start = 0; start < str.length(); start++) {
	// 0으로 시작하면 안 됨.
	if (str.charAt(start) == '0') {
	continue;
	}
	String res = "";
	for (int i = start; i < str.length(); i++) {
	res += str.charAt(i);
	if (!res.equals(str)) {
	set.add(res);
	}
	}
	}
	Iterator<String> it = set.iterator();
	int min = Integer.MAX_VALUE;
	while (it.hasNext()) {
	int num = Integer.parseInt(str);
	int temp = Integer.parseInt(it.next());
	// 다음 게임의 상황이 패배하면,
	// 현재 게임은 반드시 승리함.
	if (dp[num - temp] == 0) {
	min = Math.min(min, temp);
	}
	}
	if (min != Integer.MAX_VALUE) {
	dp[n] = min;
	}
	}
	bw.write(dp[N] == 0 ? "-1\n" : (dp[N] + "\n"));
	}
	bw.flush();
	bw.close();
	br.close();
	}
	}

view raw 1519.java hosted with ❤ by GitHub

 

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