[BOJ] C++ 9655: 돌 게임 - 쉬운 DP문제

9655번: 돌 게임

---

예제를 좀 손으로 써보면 바로 규칙이 보인다. 완벽하게라는 말에 빠져들면 좀 돌아갈 수 있는데 그냥 간단하게 우선권이 상근이한테 있고, 두 명 모두 최대한 자기가 이길 수 있는 수를 둔다는 뜻이다.

 

돌이 5개 이하일 때는 바로 답이 보이므로 돌 6개부터 보자. 상근이가 처음에 돌을 1개 가져가면 창영이는 5개에 대해 게임을 시작한다. 상근이가 3개를 가져가면 창영이는 3개로 시작한다. 5개로 시작하는 경우 시작하는 사람이 이긴다. 3개도 마찬가지다. 규칙이 좀 보일 텐데 바로 일반화시켜 보자.

 

k개로 상근이가 게임을 시작한다고 생각해 보자. 상근이가 1개 가져가면 창영이는 k-1개로 게임을 시작한다. 상근이가 3개를 가져가면 창영이는 k-3개로 게임을 시작한다. 여기서 k-1개나 k-3개에 대해 상근이가 이기는 돌의 수가 하나라도 있다면 상근이는 그 방법대로 진행할 것이다. 즉, 점화식은 dp [k] = dp [k-1] || dp [k-3]이다. 그런데 초기값이 1 0 1 0 1이므로 계속 1 0 1 0 1 형태로 테이블이 채워진다. 구현은 굉장히 쉽다.

/** DP 9655 돌 게임 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    if (n % 2)
        cout << "SK\n";
    else
        cout << "CY\n";
}