[BOJ / C++] 9655번 : 돌 게임

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

Solved.ac 레벨

실버 V

풀이

#include <bits/stdc++.h>

using namespace std;

int n;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    if(n % 2 == 0){
        cout << "CY";
    } else{
        cout << "SK";
    }

    return 0;
}

수기로 N의 값에 따른 상근이와 창영이의 선택의 결과를 보니 N이 홀수일 때는 상근이가, N이 짝수일 때는 창영이가 게임에서 이기는 것을 볼 수가 있다.

 

문제에서 눈 여겨 보아야 할 표현이 있는데 '완벽하게 게임을 했을 때' 라는 표현이다. 이는 두 사람 모두가 자신의 순서에 내리는 결정은 모두 최적의 수라는 것을 의미한다고 생각하면 될 것 같다. 즉 최적해를 구하는 dp 문제다. 점화식은 아무리 봐도 생각이 안나서 혹시 하는 마음에 N이 짝수인지 홀수인지만 이용했는데 맞았다...

 

9655번: 돌 게임