백준 루트 게임(16888)

루트 게임

1. 힌트

1) 최적의 방법으로 게임을 한다는 뜻은 가장 유리한 수를 고른다는 뜻입니다. 즉 상대가 절대로 이길 수 없는 선택지가 있다면 그 선택지를 고른다는 것으로도 이해할 수 있습니다.

2) 어떤 선택지가 최적의 선택지인지는 알아내기는 힘들어 보입니다. 결국 모든 선택지를 시도해봅니다.

3) $f(x)$를 정수 $x$를 받았을 때 반드시 이길 수 있는지 확인하는 함수로 정의합시다. 누구의 차례건 간에 똑같이 이 함수 하나로 확인할 수 있습니다.

2. 접근

1) dp함수 정의

$f(x)$를 정수 $x$를 받았을 때 반드시 이길 수 있는지 확인하는 함수로 정의합시다. 반환값은 $T$혹은 $F$입니다.
해당 차례의 플레이어가 할 수 있는 선택은 $1$부터 $x$보다 같거나 작은 모든 완전 제곱수 $j^2$를 시도하고 $f(x-j^2)$이 $F$인 선택을 하면 됩니다. $f(x)$는 참조적 투명성을 만족하므로 DP를 적용할 수 있고, 존재하는 부분 문제는 $10^6$개, 문제 하나의 시간 복잡도는 $10^3$이여서 $10^9$의 시간 복잡도지만 실제로는 이보다는 살짝 적습니다.

3. 구현

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		boolean[] dp = new boolean[1000001];
		for (int i = 1; i <= 1000000; i++)
			for (int j = 1; j * j <= i; j++)
				if (!dp[i - j * j]) {
					dp[i] = true;
					break;
				}
		int T = Integer.parseInt(br.readLine());
		while (T-- > 0) {
			bw.append(dp[Integer.parseInt(br.readLine())] ? "koosaga" : "cubelover");
			bw.append("\n");
		}
		System.out.print(bw);
	}

}

1) 시간 복잡도

$O(N\times \sqrt N)$