[Baekjoon] 돌 게임 3

👀 문제 설명

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력 1

6

 

예제 출력 1

SK

 

✍🏻풀이

Dynamic Programming으로 푸는 문제이다.

 

dp 배열을 선언하고, 상근이의 입장에서 N이라는 값이 들어왔을 때, 이기는지 지는지를 판별하여 dp 배열에 저장해둔다.

상근이는 N이 1, 3, 4일 때 이길 수 있다. 만약 N이 i일 때, 상근이가 진다면, i + 1, i + 3, i + 4일때는 이길 수 있다. (게임이 리셋된다고 생각)

 

dp[N]까지의 값을 저장해두고, dp[N]이 1이면 SK를, 0이면 CY를 출력한다.

 

코드

#include <stdio.h>
#include <iostream>

#define MAX 1001

using namespace std;

int N;
int dp[MAX]; // 상근이 기준 N값일 때 이기는지(1), 지는지(0) 저장하는 배열

// dp 사용
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    // 1개, 3개, 4개씩 가져갈 수 있다.
    dp[0] = 0; dp[1] = 1; dp[2] = 0; dp[3] = 1; dp[4] = 1;
    
    // 현재 상태로부터 다음 상태를 결정한다.
    for (int i = 1; i <= N; i++) {
        if (dp[i] == 0) {
            if (i + 1 <= N)
                dp[i + 1] = 1;
            if (i + 3 <= N)
                dp[i + 3] = 1;
            if (i + 4 <= N)
                dp[i + 4] = 1;
        }
    }
    
    /**
    if (dp[N] == 1)
        cout << "SK" << "\n";
    else
        cout << "CY" << "\n";
    */
    cout << ((dp[N] == 1) ? "SK" : "CY") << "\n";
    
    return 0;
}