[Algorithm]Baekjoon 9658번 :: 돌 게임4

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

9658번: 돌 게임 4

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n;
int dp[1001][3] = { 0 };
 
 
int DFS(int count, int turn)
{
    int opponent = turn % 2 + 1;
 
    if (dp[count][turn] != 0) return dp[count][turn];
 
    int a = 0;
    int b = 0;
    int c = 0;
 
    if (count - 1 >= 0)
    {
        a = DFS(count - 1, opponent);
    }
 
    if (count - 3 >= 0)
    {
        b = DFS(count - 3, opponent);
    }
 
    if (count - 4 >= 0)
    {
        c = DFS(count - 4, opponent);
    }
 
    if (a == turn || b == turn || c == turn)
    {
        dp[count][turn] = turn;
        dp[count][opponent] = opponent;
 
        return turn;
    }
    else
    {
        dp[count][turn] = opponent;
        dp[count][opponent] = turn;
 
        return opponent;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    dp[1][1] = 2; // 1개 남았을 때 상근이턴이면, 반드시 창용이가 승.
    dp[1][2] = 1;
    
    dp[2][1] = 1; // 2개 남았을 때 상근이 턴이면, 반드시 상근이 승.
    dp[2][2] = 2;
 
    dp[3][1] = 2;
    dp[3][2] = 1;
 
    dp[4][1] = 1;
    dp[4][2] = 2;
 
    int result = DFS(n, 1);
 
    if (result == 1) cout << "SK";
    else cout << "CY";
}

 

돌 게임 3과 거의 같은문제이다. 

일단 생각나는 그대로 직관적으로 Top-Down방식으로 풀이했다.

dp[i][j]는 i개수의 돌이 남았을 때 j의 차례이면 누가 이겼느냐가 저장되어있다.

dp[4][1] = 1 이라면, 돌이 4개 남았을 때 상근이차례라면( 상근이가 1, 창용2), 상근이가 승리한다는 의미이다.

 

Bottom-Up방식으로도 풀이 해봤다.

이 경우 코드는 훨씬 간단하지만, 개념은 좀 더 복잡하다고 생각된다.

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n;
bool dp[1001] = { false };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    // true는 선공, false는 후공.
    dp[2] = dp[4] = true; // 2개, 4개 남았을 때는 선공인 사람이 이긴다.
 
    for (int i = 5; i <= n; ++i)
    {
        if (dp[i - 1] == false || dp[i - 3] == false || dp[i - 4] == false)
        {
            dp[i] = true;
        }
    }
 
    if (dp[n]) cout << "SK";
    else cout << "CY";
}

 

여기서 dp[i] = true일 경우, i개수의 돌이 남았을 때 '선공'이 이긴다는 뜻이다. 

그렇기 때문에 일단 dp[2], dp[4]에 true값을 넣어주자.

이 게임은 무조건 상근이가 선공인데, 돌멩이가 2개면 상근이가 1개, 창용이가 마지막으로 1개를 가져가기 때문에 상근이가 승리한다.

즉, 돌멩이가 2개라면 선공인 '상근이'가 이긴다는 것보다는, '선공'인 상근이가 이긴다는 것에 중점을 둬야한다.

돌멩이가 4개일때도 마찬가지다.

 

미리 작은n값들에 대해서 업데이트 해놓은 후, 5부터 dp테이블을 업데이트 해보자.

돌멩이가 5개일 경우, 상근이는 선공이니까 1개,3개 혹은 4개를 집어들 수 있다.

이 때 1개를 집어들었다고 생각해보자.

5개일 때 선공이였으니까 1개를 집어든 이후인 4개때에는 '후공'이다.

근데 우리는 이전에 dp테이블에 dp[4] = true 값을 넣어놨었다.

즉, 4개 남았을 때에는 '선공'이 이긴다. '후공'은 무조건 진다.

우리는 돌을 집어든 후인 '후공'이기 때문에, 후공은 무조건 지게 되버리는 true값을 피해야 한다.

 

요약하면, dp[i-1], dp[i-3], dp[i-4]의 값들 중 후공이 이기는 값인 false를 찾아야 한다.

우리는 i개일 때 선공인 것이고, 1개,3개 혹은 4개의 돌을 집어든 후에는 후공의 입장이 되버리기 때문이다.

 

서로 최선의 게임을 진행하기 때문에, 단하나라도 이기는 경우의 수가 존재하면 그 루트로 파고들면 된다.

그래서 하나라도 후공이 이기는경우를 찾으면 현재 dp값(dp[i])에다가 true로 업데이트시켜주면 된다.