16888 루트 게임

각 턴에서 각 사람은 1보다 크거나 같은 완전제곱수 x를 하나 고르고, N에서 x를 뺀다. 정수는 0보다 작아질 수 없으며, 0을 만드는 사람이 게임을 이긴다.

두 사람이 모두 최적의 방법으로 게임을 했을 때, 이기는 사람이 누구인지 구하는 프로그램을 작성하시오.

 

#include <iostream>
using namespace std;
int T;
bool dp[1000001];
int main() {
    ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	dp[0] = false;
	for(int i = 1; i <= 1000001; i++){
		for(int j = 1; j * j <= i;j++){
			if(!dp[i - j * j]) {  // or dp[i + j * j] = true;
				dp[i] = true; 
				break;
			}
		}
	}
	while(T--){
	int N; cin>>N;
	if(dp[N]) cout<<"koosaga\n";
	else cout<<"cubelover\n";
	}
	return 0;
}