개요

백준 9655 (돌게임)

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

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

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

접근 방식

1. 이전 턴의 개념이 확실히 존재해서 DP로 접근해보려햇다.

2. 게임 횟수만 알면 시작이 상근이고 번갈아 하는 게임이므로 마지막에 누가 플레이하는지 알 수 있다.
   게임 횟수로 dp 배열을 만들고,

   dp[i] = Min(dp[i-1] + 1 , dp[i-3] + 1)

   이런 식으로, 첫번째 전과 3번째 전의 게임 횟수 +1 중에 적은 걸로 골랐다.

3. 그래서 초기값을 세팅하기 위해 dp[0], dp[1]값을 계산하던 중
   혹시 하는 마음에 쭈욱 계산해 보니 그냥 상근과 창영이가 번갈아서 나왔다.
   단순히 홀수면 상근, 짝수면 창영이였다.

전체 코드(DP)

#include<iostream>
#include<algorithm>
using namespace std;
//게임 횟수
int dp[1001];
int N;
int main(){
    cin>>N;

    dp[1]=1;
    dp[2]=2;
    dp[3]=3;

    for(int i=4;i<1001;i++){
        dp[i] = min(dp[i-1]+1,dp[i-3]+1);
    }
    if(dp[N]%2 ==0) cout<<"CY";
    else cout<<"SK";

}

전체 코드(홀짝)

#include<iostream>

using namespace std;
int N;
int main(){
    cin>>N;

    if(N%2 ==0) cout<<"CY";
    else cout<<"SK";

}