[Gold II] 부분 문자열 뽑기 게임 - 1519

문제 링크

성능 요약

메모리: 323276 KB, 시간: 2424 ms

분류

다이나믹 프로그래밍, 게임 이론, 문자열

제출 일자

2024년 12월 25일 04:21:35

문제 설명

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

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

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

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

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

입력

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

출력

정답을 출력한다.

문제 풀이

이미 계산된 값이면 바로 반환 (메모이제이션)
num이 9 이하면 -1 반환

• 현재 숫자의 모든 가능한 부분 문자열 생성:
  • 앞자리가 0이 아닌 모든 부분 문자열을 만듦
  • HashSet을 사용해 중복 제거

각 부분 문자열에 대해:

• 원래 숫자보다 작은 경우에만 처리
  • (원래 숫자 - 현재 부분 문자열)을 재귀적으로 확인
  • 결과가 -1이면 항상 이전은 이기므로 이 부분 문자열을 후보값으로 저장
    가능한 후보값 최소값 갱신

시간복잡도 : O(N * L²) (N: 입력값, L: 자릿수)

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int N, dp[];

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
//		br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());

		if (N < 10)
			bw.write("-1");
		else {
			dp = new int [N+1];
			int res = getMinNum(N);
			bw.write(String.valueOf(res));
		}

		bw.flush();
		bw.close();
		br.close();
	}

	private int getMinNum(int num) {
		if(dp[num] != 0) return dp[num];
		
		if(num <= 9) {
			dp[num] = -1;
			return dp[num];
		}

		String s = String.valueOf(num);
		Set<Integer> subset = new HashSet<>();
		
		for(int i=0; i<s.length(); i++) {
			if(s.charAt(i) == '0') continue;
			StringBuilder sb = new StringBuilder();
			
			for(int j=i; j<s.length(); j++) {
				sb.append(s.charAt(j));
				if(!sb.toString().equals(s)) subset.add(Integer.parseInt(sb.toString()));
			}
		}
		
		int min = Integer.MAX_VALUE;
		for(int curr : subset) {
			if(curr < num) {
				int nextNum = num - curr;
				int nextVal = getMinNum(nextNum);
				
				if(nextVal == -1) min = Math.min(min, curr);
			}
		}
		
		dp[num] = (min == Integer.MAX_VALUE) ? -1 : min;
		return dp[num];
	}
}