아이디어

• 게임 이론: 모든 플레이어가 최선의 선택을 함을 가정한다.
• 부분문자열을 만들수 없을 때, 즉 게임판에 0~9의 수가 적혀있으면 패배한다.
• i의 진부분문자열 ps에 대해
  • i - ps가 패배한다면 i는 플레이어 1이 승리하는 수다.
  • i - ps가 승리한다면 다음 턴에서 플레이어 2가 i - ps의 진부분문자열 중 승리하는 수를 고를 것이므로 i는 플레이어가 1이 패배하는 수다.
• 즉, 10 이상의 수 N과 N의 진부분문자열 ps에 대해 N - ps가 패배하는 가장 작은 ps를 골라야 한다.
  • 고를 수 있다면 게임판에 N이 적혀 있을 때 ps를 고르면 이긴다.
  • 고를 수 없다면 무슨 수를 선택하든 패배한다.
• 부분 최적 문제, 중복 부분 문제의 성질을 만족하므로 DP를 이용한다.
  • memo[i]가 0일 때 숫자 i 상태에서 이길 수 없다는 것을 나타내고, 0이 아닐 때는 고를 수 있는 진부분문자열 중 가장 작은 수를 나타내자.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.SortedSet;
import java.util.TreeSet;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	
	static int N, ans;

    // 0이면 패배, 0이 아닌 수면 승리할 수 있는 수 중 가장 작은 수
	static int[] memo;
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		memo = new int[N+1];
		
		// i = 0..9에 대해 memo = 0;
		for (int i=10; i<=N; i++) {
			for (int ps: properSubstrings(i)) {
				if (memo[i - ps] == 0) {// i - ps가 나오면 지게 됨
					memo[i] = ps;
					break;
				}
			}
		}
		
		if (memo[N] == 0) {
			System.out.println(-1);
		} else {
			System.out.println(memo[N]);
		}

	}
	
	static int[] digits = new int[7];
	static SortedSet<Integer> properSubstrings(int n) {
		SortedSet<Integer> set = new TreeSet<>();
		int tmp = n;
		for (int i=0; i<7; i++) {
			digits[6-i] = tmp % 10;
			tmp /= 10;
		}
		
		for (int i=0; i<7; i++) {
			for (int j=i; j<7; j++) {
				int num = 0;
				for (int k=i; k<=j; k++) {
					num = num * 10 + digits[k];
				}
				set.add(num);
			}
		}
		
		set.remove(0);	// 0과 자기 자신은 미포함
		set.remove(n);

		return set;
	}
}

메모리 및 시간

• 메모리: 308944 KB
• 시간: 1536 ms

리뷰

• 플레이어가 2명이 나오길래 memo를 2개 만들어야 하나 고민했지만 아니었다.
  • 플레이어 1의 승리/패배 여부에만 초점을 맞추면 되었다.
• i - ps가 승리할 때에 반드시 i가 패배한다는 것이 바로 떠오르지 않아 어려웠다.
• 메모리, 시간이 유달리 큰데, 최적화할 방법은 없을까?