백준 9655번 돌 게임 C++/DP/실버5

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

9655번: 돌 게임

 

아이디어

사실 돌의 개수를 1부터 시작해서 조금씩 늘려가다보면

돌이 홀수면 상근이 짝수면 창영이가 이긴다.

 

그래서 간단히 n 을 2로 나누고 바로 답을 출력해도 되는데

dp 문제이므로 dp 문제로 풀어보자면

dp 배열에 게임의 횟수를 계산한다.

 

0,1,2 판 일때의 게임 횟수를 계산해놓고

 

3번째 부터 돌을 1개 가져갈 경우와 3개 가져갈 경우 중 게임이 더 적게 플레이되는 경우에 + 1 한 값을 더한다.

 

나온 값으로 게임 횟수가 짝수 홀수 인지에 따라 답을 출력한다.

 

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char* argv[]) {

    ios_base::sync_with_stdio(false);
    
    int dp[1001]; // 게임 횟수
    int n;
    cin >> n;

    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = min(dp[i - 1] + 1, dp[i - 3] + 1);
    }

    // 횟수가 홀수면 상근 짝수면 창용
    if (dp[n]%2==1)cout << "SK";
    else cout << "CY";

    return 0;
}