[백준] 9658번 돌 게임 4

문제 출처: https://www.acmicpc.net/problem/9658

9658번: 돌 게임 4

----base condition----

arr[1] = 1; -->지금 차례가 패배 

arr[2] = 0; -->지금 차례가 승리

arr[3] = 1; --> 지금 차례가 패배

arr[4] = 0; --> 지금 차례가 승리

----------------------------

arr[5]부터는  1개, 3개, 4개를 뽑을수 있다 각각 뽑아본다면

arr[5-1] = 0; --> 현재 A차례라 할때 A가 5개에서 1개를 뽑는다면 4개가 남고 B차례가 된다 arr[4]는 0이기 때문에 현재 차례인 B가 승리하게된다.

arr[5-3] = 0; --> 위와 동일하게 B가 승리하게 된다.

arr[5-4] = 1; --> 현재 A차례라 할때 A가 5개에서 4개를 뽑는다면 1개가 남고 B차례가 된다 arr[1]은 1이기 때문에 B가 패배하게 된다.

두 사람은 완벽하게 게임을 하므로 무조건 자기가 이기는 쪽으로 선택을 한다.

따라서 arr[5]에서 4개를 가져간다고 하면 지금 차례가 이길수 있으므로 0이 된다.

해당 방법으로 N까지 돌려 정답을 출력한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>

using namespace std;



int main() {
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int arr[1001];
    //0 지금 차례가 승리 1 지금 차례가 패배
    arr[1] = 1;
    arr[2] = 0;
    arr[3] = 1;
    arr[4] = 0;
    int N; cin >> N;
    for (int i = 5; i <= N; i++) {
        if (arr[i - 1] == 1) {
            arr[i] = 0;
        }
        else if (arr[i - 3]==1) {
            arr[i] = 0;
        }
        else if (arr[i - 4]) {
            arr[i] = 0;
        }
        else {
            arr[i] = 1;
        }
    }

    if (arr[N] == 0)cout << "SK";
    else cout << "CY";
    
}