백준 9655 (돌 게임) c++

문제

9655번: 돌 게임

상근이와 창영이가 주어진 n개의 돌을 서로 번갈아 돌아가면 1개 또는 3개의 돌을 가져올 수 있는데 마지막으로

돌을 가져가는 사람이 이기는 게임입니다. 여기서 돌의 갯수 n이 주어졌을 때 이기는 사람을 구하는 문제입니다.

선공은 항상 상근이가 합니다.

 

dp로 접근하였습니다.

dp[x] : 돌이 x개 있는 게임판에서 선공이 이긴다면 true, 아니라면 false를 저장합니다.

초기 조건은 dp[1] = true, dp[2] = false, dp[3] = true로 잡아줍니다.

 

dp[x-1]이 false이거나 dp[x-3]이 false이면 dp[x]는 true이고, 아니라면 dp[x]는 false 입니다.

왜냐하면 돌이 x-1개 있을 때 선공이 지는 경우면 x개 있을때는 돌이 1개 더 있으므로 선공은 그 1개를 더 갖고

마지막 턴을 상대방에게 넘겨주어 상대방은 결국 마지막에 남은 돌을 가져가기 때문입니다.

마찬가지로 돌이 x-3개 있을 때 선공이 지는 경우면 x개 있을 때는 돌이 3개 더 있으므로 선공은 그 3개를 더 갖고

마지막  턴을 상대방에게 넘겨주어 상대방은 결국 마지막에 남은 돌을 가져가기 때문입니다.

---

전체 코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
using namespace std;
using ll = long long;
using ull = unsigned long long;
bool dp[1001];
int n;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    dp[1] = dp[3] = true;
    for (int i = 4; i <= n; i++)
        if (!dp[i - 1] || !dp[i - 3])
            dp[i] = true;
    if (dp[n])
        cout << "SK";
    else cout << "CY";
    
    return 0;
}