[백준] 9660번 돌 게임 6

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

9660번: 돌 게임 6

N이 1억정도라면 O(N)으로 탐색이 가능하지만 N이 매우 큰 수가 들어와서 기존 돌게임과 다른 방법이 필요하다.

기존 풀이로 작성한 코드로 arr을 출력해보면 규칙이 발견된다.

arr[0]= ?

arr[1]= 1

arr[2]= 0

arr[3]= 1

arr[4]= 1

arr[5]= 1

arr[6]= 1

 

arr[7]= 0

arr[8]= 1

arr[9]= 0

arr[10]=1

arr[11]=1

arr[12]=1

arr[13]=1

 

arr[0]이 0이라고 생각하면 0101111이 계속 반복되는 규칙성이 보인다.

따라서 arr[N] == arr[N%7]임을 알 수 있다.

#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];
    //1 자기 차례에 승리
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 0;
    arr[3] = 1;
    arr[4] = 1;
    long long N; cin >> N;
    for (int i = 5; i <= 6; i++) {
        if (arr[i - 1] == 0) {
            arr[i] = 1;
        }
        else if (arr[i - 3]==0) {
            arr[i] = 1;
        }
        else if (arr[i - 4]==0) {
            arr[i] = 1;
        }
        else {
            arr[i] = 0;
        }
    }

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