[백준/Baekjoon] 9657 돌 게임 3 C++ :: Dynamic Programming

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

9657번: 돌 게임 3

---

1. Logic

먼저 dp테이블의 의미는 dp[i] i개의 돌에서 턴을 잡은 사람의 승패 유무이다.

문제에서 1개, 3개, 4개를 가져갈 수 있다고 했고 항상 상근이가 먼저 시작한다고 했기 때문에 

돌 갯수 | 우승자

1개 | 상근이

2개 | 창영이

3개 | 상근이

4개 | 상근이

항상 이렇게 이기고 이후는 이전에 메모이제이션 된 값으로 부분문제가 쪼개지기 때문에 DP로 풀 수 있다.

항상 두 사람이 완벽하게 게임을 한다고 했으며 항상 상근이가 먼저 시작하기 때문에 한번이라도 상근이가 이기는 경우가 생기면 해당 n개의 돌에서는 상근이가 항상 이길 수 있다.

 

---

2. Code

#include <cstring>
#include <iostream>

using namespace std;

int n;
const int INF = 987654321;
// 0이면 sk 1이면 cy
int dp[1001];

// 상근이가 이기는 경우는 1, 아닌 경우는 0으로 표시
int solve(int stones) {
    if(stones == 0) return 0;
    if(stones == 1) return 1;
    if(stones == 2) return 0;
    if(stones == 3) return 1;

    int &ret = dp[stones];
    if(ret != -1) return ret;

    ret = !solve(stones - 1) || !solve(stones - 3) || !solve(stones - 4);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    cin >> n;
    
    if(solve(n)) cout << "SK";
    else cout << "CY";
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90