[C++/백준] 9657번: 돌 게임 3

문제 링크

9657번: 돌 게임 3

 

풀이

DP 문제

1. 일단 돌을 1개, 3개, 4개 주을 수 있으니 dp[1] ~ dp[4]까지는 초기화해준다.
   1. dp에는 게임이 몇 번만에 끝나는지가 들어있다.
   2. 1개면 상근이가 1개를 줍고 끝나서 1, 2개면 상근이가 1개, 창영이가 1개 주워서 두 번만에 끝나니 2인 식이다.
2. n까지 dp를 구하는데, 상근이가 1개를 주웠을 때 dp[i-1], 그니까 i-1개 남았을 때에서 상근이가 한 번 주운 1을 더해서 홀수가 되면 상근이가 이기는 거고, 아니면 창영이가 이기는 것이다.
3. 첫빠따는 상근이기 때문에 dp[i-1], dp[i-3], dp[i-4]를 다 확인해보면서 홀수가 하나라도 나오면 상근이가 이길 것이다.

 

코드

#include <iostream>

using namespace std;

int dp[1001]; // 몇 번만에 게임이 끝나는지

int main()
{
    int n;
    cin >> n;

    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 1;
    dp[4] = 1;

    for (int i = 5; i <= n; i++)
    {
        // 상근이가 1, 3, 4개 잡았을 때 dp[남은 돌] + 1이 홀수면 상근이가 이김
        if ((dp[i - 1] + 1) % 2 == 1)
        {
            dp[i] = dp[i - 1] + 1;
        }
        else if ((dp[i - 3] + 1) % 2 == 1)
        {
            dp[i] = dp[i - 3] + 1;
        }
        else if ((dp[i - 4] + 1) % 2 == 1)
        {
            dp[i] = dp[i - 4] + 1;
        }
        else // 창영이가 이김
        {
            dp[i] = dp[i - 1] + 1;
        }
    }

    if (dp[n] % 2 == 1)
    {
        cout << "SK";
    }
    else
    {
        cout << "CY";
    }
}