[ 백준 9656 ] 돌 게임2 (C++)

백준의 돌 게임2(9656) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

간단한 수식을 이용해서 문제에 접근해보자.

F[A] = 0 / 1 이라는 수식을 사용할 것인데, F[A] = 0의 의미는 "돌이 A개가 있을 때, 상근이가 이길 수 없습니다." 를 의미하고, F[A] = 1의 의미는 "돌이 A개가 있을 때, 상근이가 이길 수 있습니다." 를 의미한다.

즉, 우리가 구하고자 하는 답은 F[N] = 0 이라면 상근이가 이길 수 없다는 것을 의미하고, 이는 곧 창영이가 이긴다는 것을 의미하므로 "CY"를, F[N] = 1이라면 상근이가 이길 수 있음을 의미하므로 "SK"을 출력하면 된다.

먼저, 돌이 1개가 있는 상황부터 가정해보자.

돌이 1개가 있을 때, 상근이부터 돌을 1개 or 3개를 가져가 된다.

일단, 돌이 1개밖에 없으니 상근이는 반드시 해당 돌 1개를 가져가야만 한다.

즉, 이 순간 마지막 돌을 상근이가 가져간 것이므로, 이 경우에는 창영이가 이기게 된다.

따라서 F[1] = 0 이 된다.

돌이 2개가 있는 상황을 생각해보자.

돌이 2개가 있을 때, 상근이 부터 돌을 1개 or 3개를 가져가게 되는데, 돌이 3개가 되지 않으니, 반드시 상근이는 돌을 1개만 가져갈 수 밖에 없다. 그럼, 돌이 1개가 남을테고, 이를 창영이가 가져가게 되니, 이 경우에는 상근이가 승리하게 된다.

F[2] = 1

돌이 3개가 있는 상황을 생각해보자.

돌이 3개가 있을 때는, 상근이에게 2가지 선택권이 주어진다.

1. 돌을 1개만 가져가는 경우

2. 돌을 3개 모두 가져가는 경우

상근이가 정말 이기고 싶다면 2번 경우를 선택하지는 않을 것이다. 왜냐하면 돌이 3개가 있는데, 첫 턴에 돌 3개를 모두 가져가 버리면 상근이가 지게 되는 것이기 때문에, 아마 돌을 1개만 가져가는 선택을 할 것이다.

그럼, 돌을 1개만 가져갔다고 가정해보자. 그럼 돌이 2개가 남게되는데 ,창영이는 여기서 1개의 돌을 가져갈 것이고, 마지막 남은 1개의 돌을 다시 상근이가 가져가게 된다. 즉, 상근이가 1번경우처럼 돌을 1개만 가져가던지, 2번경우처럼 돌 3개를 모두 가져가던지 결국에는 절대로 이길 수가 없다.

F[3] = 0

돌이 4개가 있는 상황을 생각해보자.

먼저, 누가 이기는지는 둘째 치고, 돌 4개를 상근이와 창영이가 가져가는 모든 경우에 대해서 알아보자.

그 모든 경우를 나열해 본다면...

1. 상근이가 1개 - 창영이가 1개 - 상근이가 1개 - 창영이가 1개 = 상근 승

2. 상근이가 1개 - 창영이가 3개 = 상근 승

3. 상근이가 3개 - 창영이가 1개 = 상근 승

위와 같이 3가지 경우가 발생하는데, 모두 상근이의 승리로 끝난다는 것을 알 수 있다.

그럼 여기서 규칙을 한번 찾아보자.

먼저 1번과 2번 경우를 보면 공통점이 하나 있다.

바로, "첫 번째 턴에서 상근이가 돌을 1개만 가져감으로써 남은 돌이 3개가 되도록 만든다" 는 것이다.

또한, 돌이 3개가 남아있을 때, 창영이의 턴이라면, 이는 무조건 상근이가 승리한다는 것도 알 수 있다.

반대로 3번 같은 경우에는, "첫 번째 턴에서 상근이가 돌을 3개 가져감으로써 남은 돌이 1개가 되도록 만든다" 는 것이다.

또한, 돌이 1개가 남아있을 때, 창영이의 턴이라면, 이는 무조건 상근이가 승리한다는 것을 의미한다.

즉 ! 승패는 돌이 N개가 주어졌을 때, 돌이 N - 1개 혹은 N - 3개가 남았을 때, 누구의 턴이냐 ? 에 따라서 승패가 갈라진다는 것이다. N - 1개가 남든, N -3개가 남든, 해당 턴 사람은 반드시 패배하게 되어있다.

그럼 누구의 턴인지 어떻게 알 수 있을까 ?? 그리고 결과적으로 누가 이기는지 어떻게 알 수 있을까 ??

사실, 누구의 턴인지는 알기가 힘들다. 하지만, 우리는 기존의 결과들로 누가 이기는지 알 수가 있다.

F[1] = 0 이고 F[3] = 0 이었다. 즉, 돌이 1개 혹은 3개가 있을 때는, 상근이가 반드시 패배했었다.

그런데, 돌이 4개가 있을 때는 상근이가 승리하게 된다.

즉 ! 돌이 N개가 주어졌을 때, N - 1개가 주어졌을 때, 혹은 N - 3개가 주어졌을 때 패배한 사람이 반드시 승리한다는 것이다.

위의 돌이 4개인 경우도 한번 해보면, F[4 - 1] = F[3] = 0 , F[4 - 3] = F[1] = 0 으로, 돌이 1개 , 3개일때는 상근이가 패배했지만, 이 경우에는 승리하게 된다.

그럼 돌 5개로 위의 식을 한번 확인해보자.

F[5]를 구하기 위해서, F[5 - 1]과 F[5 - 3]의 값을 가져와보자.

F[5 - 1] = F[4] = 1 (상근이의 승리 = 창영이의 패배)

F[5 - 3] = F[2] = 1 (상근이의 승리 = 창영이의 패배)

즉, 돌이 5개가 있을 때, 결과를 구하기 위해서 돌이 2개 있을때와 4개있을 때의 결과값을 보니, 창영이가 패배한다고 되어있다. 그럼, 5개가 있을 때는 반드시 창영이가 승리하게 될 것이다.

실제로 확인해보자.

돌 5개를 가져가는 경우의 수

1. 상근이가 1개 - 창영이가 1개 - 상근이가 1개 - 창영이가 1개 - 상근이가 1개 = 창영이의 승리

2. 상근이가 1개 - 창영이가 1개 - 상근이가 3개 = 창영이의 승리

3. 상근이가 1개 - 창영이가 3개 - 상근이가 1개 = 창영이의 승리

4. 상근이가 3개 - 창영이가 1개 - 상근이가 1개 = 창영이의 승리

위의 결과와 같이 누가 어떻게 가져가든지 반드시 창영이의 승리로 끝나게 된다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N;
int DP[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    DP[1] = 0;
    DP[2] = 1;
    DP[3] = 0;
    for (int i = 4; i <= N; i++)
    {
        if (DP[i - 1] == 0 || DP[i - 3] == 0) DP[i] = 1;
        else DP[i] = 0;
    }
 
    if (DP[N] == 1) cout << "SK" << endl;
    else cout << "CY" << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}