백준 : 1519

www.acmicpc.net/problem/1519

1519번: 부분 문자열 뽑기 게임

오랜만에 문제 풀어봄..

 

탑 다운 메모이제이션으로 풀었고 

 

현재 내턴에서 n - 연속된수 한 결과가 -1 이면 내가 이긴 수라서 그중에서 가장 작은 target 값 찾는다.

 

만약 모든 결과가 -1이 없으면 어느것을 빼든 내가 지는 턴이기때문에 -1반환

 

package naver;

import java.util.Scanner;

public class B1519 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		dp = new int[1000001];
		System.out.println(Sovle(n));

	}

	/*
	 * 0 : 아직모름 -1 : 짐 ,그외 : 이김
	 */
	static int dp[];

	private static int Sovle(int n) {
		if (dp[n] != 0) {
			return dp[n];
		}

		if (n < 10) {
			return dp[n] = -1;
		}

		/*
		 * 진 부분 집합들
		 */

		int thisValue = 987654321;
		boolean victory = false;
		/*
		 * 여기서 나오는 결과값들이 전부다 패배를 나타내는 -1이 안나오면 내가진거
		 */
		String strN = n + "";
		for (int i = 1; i < strN.length(); i++) {
			for (int j = 0; j <= strN.length()-i; j++) {
				int thisN = Integer.parseInt(strN.substring(j, j+i));

				if (thisN == 0)
					continue;
				if (Sovle(n - thisN) == -1) {
					victory = true;
					thisValue = Math.min(thisValue, thisN);
				}
			}
		}

		/*
		 * -1: 패배 0: 모름 1: 승리
		 */
		if (victory == false)
			return dp[n] = -1;

		return dp[n] = thisValue;
	}
}