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

문제

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

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

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

입력

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

출력

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

Solved.ac 레벨

실버 III

풀이

#include <bits/stdc++.h>
#define MAX 1001

using namespace std;

int n;
bool dp[MAX];

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

    //상근이를 true로 본다.
    //상근이가 돌이 1, 3, 4개인 경우는 무조건 승리한다.
    dp[1] = true; 
    dp[2] = false;
    dp[3] = true;
    dp[4] = true;

    cin >> n;

    for(int i = 5; i <= n; i++){
        if(dp[i-1] && dp[i-3] && dp[i-4]) dp[i] = false;
        else dp[i] = true;
    }

    if(dp[n]) cout << "SK" << '\n';
    else cout << "CY" << '\n';

    return 0;
}

 

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

9655번의 시리즈 문제인 것 같다. 9655번의 경우에는 그냥 N이 짝수인지 홀수인지에 따라 승자가 결정되었다면, 이번 문제의 경우에는 동적계획법을 사용하지 않고는 풀기가 조금 어려운 것 같았다.

주어지는 돌이 6개인 경우까지 수기로 작성하다 보면 규칙이 보여 점화식을 어렵지 않게 도출해낼 수 있었다.

 

9657번: 돌 게임 3