백준 9655번 (돌 게임) c++

문제

문제 풀이

문제의 조건을 제대로 파악해야 한다.

1. 둘 다 각각의 차례에 1개 또는 3개를 가져갈 수 있다.

2. 두 사람이 완벽하게 게임을 플레이 한다.

3. 게임은 상근이가 먼저 시작한다.

 

N = 1             N = 2           N = 3           N = 4         N = 5        N = 6

 SK                  CY              SK               CY             SK            CY

 

이렇게 각 N에 따라 답은 정해져 있다.

규칙을 보자면 짝수일 때, 홀수일 때 각각 답이 같은 것을 알 수 있다.

 

그래서 단순히 홀수, 짝수를 판별해 답을 도출할 수 있다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int main(){

        ios_base::sync_with_stdio(false);
        cin.tie(0);

        int N;

        cin >> N;

        if(N & 1){
                cout << "SK\n";
        }
        else cout << "CY\n";

        return 0;

}

 

하지만 이 문제를 DP(Dynamic Programing)으로도 풀 수 있다.

예를 들어 N에서 1개 혹은 3개를 가져갈 수 있다.

그래서 N개의 결과는, N - 1 or N - 3의 경우일때의 결과와 반대의 경우로 설정을 해주면 된다. (물론 N - 1 이나 N - 3의 결과는 동일하다.)

나는 단순히 N - 1의 경우만을 고려하여 답을 출력했다.

 

전체코드

#include <bits/stdc++.h>

using namespace std;

int main(){

        ios_base::sync_with_stdio(false);
        cin.tie(0);

        int N;

        cin >> N;

        bool dp[1001] = {0,};

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

        for(register int i = 4; i <= N; i++){
                dp[i] = !dp[i-1];
        }

        if(dp[N]){
                cout << "SK\n";
        }

        else cout << "CY\n";


        return 0;

}