[Algorithm]Baekjoon 9657번 :: 돌 게임3

https://www.acmicpc.net/problem/9657

9657번: 돌 게임 3

 
 
 
int n;
bool dp[1001] = { false,true,false,true,true };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 5; i <= n; ++i)
    {
        dp[i] = false;
 
        if (dp[i - 1] == false || dp[i - 3] == false || dp[i - 4] == false)
        {
            dp[i] = true;
        }
    }
 
    if (dp[n])
    {
        cout << "SK";
    }
    else
    {
        cout << "CY";
    }
}
 
 
 

 

꽤 유명한 문제들 중 하나이다. 님게임과 더불어, 게임이론 중 하나로 유명한 것 같다.

서로 턴을 번갈아가면서 1 ~ k(임의의 숫자) 씩 가져갔을 때, 누가 이기는지 구하는 게임이다.

마지막돌을 가져간사람이 승리하거나, 패배하는 등 조건은 문제마다 조금씩 다르지만 규칙은 거의 동일하다.

술게임중 하나인 베스킨라빈스31 을 떠올리면 된다.

이론상, 두명이 한다고 했을 때 공식을 알고있으면 반드시 처음 시작하는사람이 이길 수 있다.

 

이번 문제같은경우는 각 차례마다 1개나 3개,혹은 4개를 가져갈 수 있다.

즉 남은 돌 개수가 1개,3개,4개라면 해당 턴인 사람이 반드시 승리한다.

그리고 무조건 상근이가 처음 시작한다. 그렇기때문에 처음 주어지는 n값이 1,3,4면 무조건 상근이가 이긴다.

n값이 2면 창용이가 이긴다. 2면 상근이가 1을 선택할 수 밖에 없고, 그러면 1개가 남으며 해당 턴은 창용이턴이 되어 나머지 1개를 집으면서 창용이의 승리로 끝나게 된다.

 

여기서 인지해야할 것은,  1개, 3개, 4개가 남았을 때 상근이가 이긴다! 라고 생각하지말고 

1개,3개,4개 남았을 때 '해당 턴'인 사람이 이긴다.... 라고 생각해야 한다. 선공,후공개념으로 바라봐야 한다. 

돌 2개가 주어졌을 때 창용이가 이긴다는 사실을 우리는 알고 있다.(값이 작아서 바로 유추)

즉, 돌 2개가 남았을 때는 '후공'인 사람이 이긴다는 것이다. 

 

이 상태에서 돌이 5개가 주어졌다고 가정해보자.

상근이가 무조건 먼저 시작이니, 상근이가 먼저 1개를 가져갔다고 가정한다.

그러면 남은건 4개다. 4개가 남았기 때문에 해당턴인 사람이 무조건 이기는데, 해당턴에는 창용이 턴이니 무조건 창용이가 이긴다.

고로 이 선택지는 고르면 안될것이다.

 

3개를 가져갔다고 가정해보자.

그러면 남은건 2개다. 해당턴엔 창용이인데, 2개밖에없으니 1개만 가져가게된다.

그러면 1개가 남고, 다시 상근이턴이니 해당 1개를 가져감으로써 상근이가 이긴다.

 

4개를 가져갔다고 가정해보자.

남은건 1개, 해당턴은 창용이이니 창용이가 나머지 1개를 가져감으로써 승리한다.

 

이 세가지 선택지를 고려했을 때, 5개가 주어졌을 때 상근이는 먼저 선공권으로 3개를 가져가면 '반드시' 이긴다.

2개가 남았을 때 창용이는 뭔짓을 하든 '패배'하기 때문이다.

 

즉, 세가지 선택지 중 단 하나라도 최종적으로 후공인사람이 패배하는 경우가 있으면, 선공한사람이 무조건 이긴다.

왜? 게임을 이기기위해 최선을 다할거니까.

 

그러면 1차원배열인 dp테이블을 정의해보자.

여기서 dp[1] = dp[3] = dp[4] = true; dp[2] = false를 넣어주고 시작하자. 이정돈 쉽게 유추할 수 있으니까.

여기서 각각이 의미하는바가 무엇일까?

dp[1] == 1개가 주어졌을 때는 상근이가 이긴다? 틀린말은 아니다.

그러나 이렇게 해석해보자. '1개가 주어졌을 때 해당턴인 사람이 반드시 이긴다'

dp[3], dp[4]도 마찬가지다.

dp[2]는 false다. 즉, '2개가 주어졌을 때, 해당턴인 사람이 반드시 진다'..가 된다. 

 

위에서 들었던 예시로 다시 n값을 5로 놓고 보자.

 

dp[5-1] == dp[4] -> 5개가 주어진상태에서, 선공권이 있는 상근이가 1개를 먼저 집는다.

이 때 dp[4]값을 사용할건데, 상근이가 1개 집었으니 현재턴은 창용이의 턴이다. 즉 후공이다.

dp[4]에는 true값이 들어있다. 아까 말했다시피 dp[4]값이 true라는 것은, 4개가 남았을 때 상근이가 이긴다는게 아니다!

4개가 남았을 때, '해당 턴'인 사람이 이긴다는 것이다.

상근이가 먼저 1개 집어든 상태에서, 창용이턴에 4개가 남아있기 때문에 반드시 창용이가 이긴다.

즉, 우리는 해당턴의 사람이 반드시 져야하는 경우를 구해야한다.

그게 바로 dp[2]같은 경우이다. dp[2]는 2개 남았을 때, 해당턴인 사람이 지는 경우다.

 

그렇기 때문에 dp[i-1], dp[i-3], dp[i-4] 중, 하나라도 false인 값을 찾는다면 dp[i]에 상근이가 이긴다고 기록하는 것이다.

돌이 i개 일 때 상근이가 무조건 선공이기 때문에, 후공차례인 창용이는 i-1개나 i-3개, i-4개 남았을 때 단 하나의 경우라도 져야만이 상근이가 이길 수 있기 때문이다.