백준 16888: 루트 게임

https://www.acmicpc.net/problem/16888

16888번: 루트 게임

 

게임 이론 문제는 DP로 풀어야 하는 게 있고 규칙성을 찾아야 하는 게 있는데 이건 DP로 푸는 문제다.

 

STEP 0.

 

bool dp[] 배열을 생각해보자

dp[i]에는 내 차례에 숫자가 i일때 내가 이기면 true, 내가 지면 false값을 저장한다.

 

그럼 일단 dp[1]=1, dp[4]=1, dp[9]=1, ...... 모든 제곱수 i에 대해 dp[i]=1이다.

 

STEP 1.

 

i가 제곱수가 아니라면 i 이하 모든 제곱수 j에 대해 dp[i-j]값이 하나라도 0이라면 dp[i]=1이다.

dp[i-j]값이 전부 1이라면 dp[i]는 0이다.

 

상대 차례에 상대가 지는 숫자를 남길 수 있다면 내가 무조건 이기기 때문이다.

 

예를들어 1은 이기는 숫자다.

2는 지는 숫자다. 2 이하 제곱수는 1밖에 없는데 내 차례에 1을 빼면 상대편 차례에 이기는 숫자인 1이 남기 때문이다.

 

그럼 11은 이기는 숫자다.

내 차례에 숫자가 11이라면 나는 9를 빼서 지는 숫자인 2를 상대편에게 남겨줄 수 있기 때문이다.

 

이런 원리로 작은 i부터 시작해서 bottom up 방식으로 DP를 진행한다.

 

#include <vector>
#include <iostream>
#include<stdbool.h>
 
using namespace std;
 
int main()
{
    int t;
    scanf("%d", &t);
    bool dp[1000005];
    dp[0] = 0;
    vector<int> sq;
    int root = 1;
    for (int i = 1;i < 1000001;i++)
    {
        if (root * root == i)
        {
            dp[i] = 1;
            root++;
            sq.push_back(i);
            continue;
        }
        bool x = 0;
        for (auto j : sq)
        {
            x = x || !dp[i - j];
        }
        dp[i] = x;
    }
 
    for (int i = 0;i < t;i++)
    {
        int k;
        scanf("%d", &k);
        printf(dp[k] ? "koosaga\n" : "cubelover\n");
    }
}