[백준 9658][C++] 돌 게임 4

문제 링크

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

---

 

◆문제 해결 및 설명◆

문제 : 턴을 번갈아가며 돌을 1 or 3 or 4개를 뺄 수 있고, 받은 돌의 갯수가 1이면 질 때, 최선의 플레이를 하였을 경우 이기는 사람을 구하여라

 

일단 나열을 해보았다. (먼저 받은 아이가 상근)

1. 상근 패
2. 상근 승(1,1)
3. 상근 패(1,1,1)
4. 상근 승(3,1)
5. 상근 승(4,1)
6. 상근 승(3,1,1,1)
7. 상근 승(4,1,1,1)
8. 상근 ?(7,6,? // 7,4,? // 7,3,?) = 창영 승

7전까지는 3을 받는것이 아니라면 상근이가 무조건 이긴다. (최선의 플레이 상황 가로에 나열)

하지만 8부터는 애매 모호해지는데 다음 턴인 창영이가 플레이하기 때문에 6, 4, 3을 받으면 창영이가 이기게 된다.

여기서 알 수 있는것은 턴이 넘어가게 된다면 상근이의 승리였던 숫자들이 창영이가 승리할 수 있는 플랜이 된다.

 

따라서 이름을 바꿔보자. (상근 -> 받는 사람의 )

1. 받는 사람의 패
2. 받는 사람의 승(1,1)
3. 받는 사람의 패(1,1,1)
4. 받는 사람의 승(3,1)
5. 받는 사람의 승(4,1)
6. 받는 사람의 승(3,1,1,1)
7. 받는 사람의 승(4,1,1,1)
8. 받는 사람의 패(7,6,3,1,1,1 // 7,4,3,1 // 7,3,1,1,1)

이 떄  가져갈 수 있는 돌의 개수는 한정되어 있으므로 Bottom-up 방식으로 코드를 짤 수 있다. 

최선의 플레이는 받는사람이 절대 승리하는 숫자를 주면 안되는 것이므로
N  = !(N-1=win && N-3=-win && N-4=-win)
을 통해 넘겨줄 경우의 수가 전부 승리일 때 패배로 코드를 작성하였다.

 

◆코드 전문◆

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> dp(N + 1, 1);
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 0;
    dp[4] = 1;
    for (int i = 5; i <= N; i++)
    {
        if (dp[i - 1] == 1 && (dp[i - 3] == 1 && 0 < i - 3) && (dp[i - 4] == 1 && 0 < i - 4))
        {
            dp[i] = 0;
        }
    }

    if (dp[N])
    {
        cout << "SK";
    }
    else
    {
        cout << "CY";
    }
}