[백준 9655번] [동적 계획법] 돌 게임

Approach

최선의 선택을 한다는 사실을 잘 생각해보면, 결과적으로 최소한의 움직임만 고려해주면 된다.

가장 최소한의 움직임에서 움직임이 늘어나는 경우는 3이 선택되어야하는 상황에 1을 선택하는 상황인데, 최적 상황에서의 우승자는 1을 유지해주면 마지막에 고르는 것이 그대로 유지된다.

 

따라서, 최소한의 선택으로 N개를 분배하는 방법을 찾고 선택의 횟수가 홀수이면 SK, 짝수이면 CY를 출력해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int dp[1001];
int n;

int dp_value(int x){
    if(x < 1) return 987654321;
    if(dp[x] != -1) return dp[x];
    else{
        return dp[x] = min(dp_value(x - 1), dp_value(x - 3)) + 1;
    } 
}

int main(void){
    memset(dp, -1, sizeof(dp));
    dp[1] = 1;
    dp[3] = 1;
    cin >> n;
    
    int check = dp_value(n);
    if(check % 2 == 1){
        cout << "SK\n";
    }
    else{
        cout << "CY\n";
    }
    return 0;
}