BOJ 9657 돌 게임 3

08 Sep 2020 in Study on BOJ, Dp

사용한 알고리즘

DP

알고리즘 설명

단순한 DP 문제이다
돌을 뽑는 경우는 1,3,4개를 뽑을 수 있다
이 3가지 경우에서 상대방이 지는 경우가 하나라도 있으면 현재 사람은 그 선택을 할 것이다
이러한 점에서 반대로 위 3가지 모든 경우 상대방이 이기면 뽑는 사람은 진다
이러한 룰로 DP를 구성하면 다음과 같다
DP[N] = !DP[N-1] || !DP[N-3] || !DP[N-4]

풀이

#include <bits/stdc++.h>
using namespace std;

const int MAX_N=1001;

int N, dp[MAX_N];

int main() {
    scanf("%d", &N);
    dp[1]=dp[3]=dp[4]=1;
    for (int i=5; i<=N; i++)
        dp[i] = !dp[i-4] || !dp[i-3] || !dp[i-1];
    puts(dp[N] ? "SK" : "CY");
    return 0;
}