BOJ 16876 재미있는 숫자 게임

* BOJ 16876 재미있는 숫자 게임

[분류 : 다이나믹 프로그래밍]

[풀이]

  턴 수의 홀짝 여부를 따져서 누가 게임을 끝내는지 쉽게 알 수 있다. 따라서 기저 조건에 게임이 종료될 때 누가 이기는지 결정한다.

  서로 이기려고 최선을 다한다는 조건이 있기 때문에 어느 턴(p)에 어떤 수(d)로 주어지는 경우에 수행할 수 있는 행동은 1~10^3자리 숫자를 1 증가하는 4개밖에 없으므로 for문 한 번 구성해서 돌려주면 된다.

  9에서 다시 0으로 간다는 조건만 잘 구현하면 어렵지 않게 AC를 받을 수 있는 문제다.

#include<cstdio>
#include<cstring>
int dp[101][10000], N, M, dx[] = { 1,10,100,1000 };
int rec(int p, int d) {
	if (p == M) return p % 2 ? d <= N : d > N;
	int& ret = dp[p][d];
	if (ret != -1) return ret;
	ret = 0;
	int i, x, t;
	for (i = 0; i < 4; i++) {
		t = d;
		x = (d / dx[i]) % 10;
		t -= x * dx[i];
		x = (x + 1) % 10;
		t += x * dx[i];
		ret |= !rec(p + 1, t);
	}
	return ret;
}
int main() {
	memset(dp, -1, sizeof dp);
	scanf("%d%d", &N, &M);
	puts(rec(0, N) ? "koosaga" : "cubelover");
	return 0;
}