[백준] 9655번 : 돌 게임 (C++)

9655번 : 돌 게임

---

문제)

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

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

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

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

// 9655. 돌 게임
#include <iostream>
 
using namespace std;
 
int n;
bool dp[1010];
 
int main()
{
    cin >> n;
 
    // 1, 3인 경우에는 상근이가 이긴다.
    dp[1] = 1;
    dp[3] = 1;
 
    // i - 1, i - 3인 경우를 상대에게 줘버리면
    // 상대방이 이기게 된다.
    for (int i = 4; i <= n; i++)
    {
        if (!dp[i - 1] || !dp[i - 3])
        {
            dp[i] = 1;
        }
    }
 
    if (dp[n]) cout << "SK";
    else cout << "CY";
 
    return 0;
}

---

출처 : https://www.acmicpc.net/problem/9655 

9655번: 돌 게임