백준 9657번 돌게임3

돌 게임 3 

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

128 MB

4238

1949

1634

48.689%

문제

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

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

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

입력

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

출력

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

마지막에 남은 돌갯수	1	2	3	4	5	6	7	8	9
상근 시작	이김	짐	이김	이김	이김
창영 시작	이김	짐	이김	이김	이김

상근시작에서 5개가 남을 경우 상근이의 선택지는 1개선택, 3개선택, 4개선택이다.
1개를 선택했을시 4개가 창영이턴으로 넘어가고 창영시작의 표에서 남은 돌갯수가 4개일시 창영이 승리한다. 때문에 1개선택시 상근의 패배이다.
같은 맥락으로 3개를 선택했을시 2개가 창영의 턴으로 넘어가고 창영시작의 표에서 남은 돌갯수가 2개일시 창영이 패배하기때문에 상근이 승리한다.

결론적으로 총 갯수-1, -3, -4 를 했을시 상근이가 모두 이긴다면 현재 갯수에선 상근이가 패배하는 구조이다. 이를 이용해 정답을 알아내 출력한다.

#include <iostream>

using namespace std;

int dp[1000];

int main() {
    int n;
    cin >> n;
    dp[1] = dp[3] = dp[4] = 1;
    
    for(int i=5; i<n; i++){
        if(!(dp[i-1]&& dp[i-3]&& dp[i-4])){
            dp[i] = 1;
        }
    }
    if(dp[n]){
        cout << "SK";
    }else {
        cout << "CY";
    }
    
    return 0;
    
}