[백준 9656번] 돌 게임 2 (C++)

문제링크 : https://www.acmicpc.net/problem/9656

9656번: 돌 게임 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int dp[1001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N;
    cin >> N;
    
    dp[1] = 0; //결과가 0이면 창영, 결과가 1이면 상근이 승리
    dp[2] = 1;
    dp[3] = 0;

    for(int i=4; i<=N; i++)
    {
        if(dp[i-1] == 1 || dp[i-3] == 1) dp[i] = 0;
        else dp[i] = 1;
    }

    cout << (dp[N]==1 ? "SK" : "CY");
    return 0;
}

돌게임 문제이다 dp를 활용한다.

여기서 주의해야할 것은 두 사람이 게임을 완벽하게 한다는 것이다.

 

따라서 처음 초기값을 결과값에 따라 누가 이길 것인지를 미리 정해준다.

그리고 이전 값에 따라 현재 값을 반대로 갱신하고 출력해준다.