백준 BOJ 9660 - 돌 게임 6

범위가 터무니없어서 의심이 갔던 문제.

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

9660번: 돌 게임 6

풀고나서 확인해보니 돌 게임3의 확장버전이라고 한다

돌 게임 3도 풀고 와야지 히히

범위가 하도 터무니 없다는 점에서 무언가 꼼수가 있겠다 싶어

일단 100개 정도만 dp를 통해서 구해보았다.

 

dp를 통해 구한 방법은

dp[k-1], dp[k-3], dp[k-4] 중에 창영이가 반드시 승리하는 경우가 있다면

상근이의 승리, 아니라면 창영이의 승리에 해당한다.

중요한것은 아니니 짧게 적어보고

 

암튼 해당 방법을 통해서 구해놓고 보니 알수 있었던 점으로

1111 네개가 붙어있는게 규칙적으로 반복된다는 게 쉽게 눈에 보이고,

주기가 7인 "1011110"이 규칙적으로 반복됨을 알 수 있다.

 

1을 상근, 0을 창영이에 매칭해뒀으므로

N을 입력받아서 7으로 나눈 나머지가 0, 2인경우 창영이의 승리,

아닌경우 상근이의 승리가 되겠다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ll N;
	cin >> N;
	
	/*
	int dp[100] = {0};
	dp[1] = 1; // 1-상근 0-창영
	dp[2] = 0;
	dp[3] = 1;
	dp[4] = 1;
	for(int i=5; i<=100; i++){
		if(!dp[i-1] || !dp[i-3] || !dp[i-4]) dp[i]=1;
		else dp[i]=0;
	}
	for(int i=1; i<100; i++) cout << dp[i];
	*/
	
	N %= 7;
	if(N == 2 || N == 0) cout << "CY";
	else cout << "SK";
	return 0;
}

이 문제와 돌 게임 3을 통해서 최종적으로 1000솔을 달성하지 싶다