백준(BOJ) 9660 : 돌 게임 6

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

9660번: 돌 게임 6

 

 

백준에는 돌 게임이 참 많다.

이 문제는 solved.ac 기준으로 골드5의 난이도를 가지고 있는데 실버에 속한 돌 게임과의 차이점은 N의 범위가 굉장히 크다는 것이다.

따라서 O(N)의 풀이조차도 TLE가 발생한다.

이런 게임이론 같은 경우에는 규칙을 찾아 푸는 것이 가장 편한 방법인 듯하다. 못찾으면 난이도가 급상승하니..

수학적으로 머리가 비상해서 규칙만 읽고 규칙을 찾을수만 있다면 정말 좋겠지만 필자는 똑똑이가 아니라서 적당한 탐색을 통해 규칙을 찾기로 했다.

 

우선 돌이 1~4개 있을 때를 생각해보자.

마지막 돌을 가져가는사람이 승리하니 돌이 1, 3, 4 개면 무조건 그 차례의 사람이 승리하고 2개면 패배한다.

 

그럼 나머지의 경우는 어떨까?

만약 돌이 5개 있었다고 생각해보자. 5개에서 다음 차례로 넘길 수 있는 경우의 수는 1개, 2개, 4개이다. (1,3,4개 가져갈 수 있으므로) 근데 위에서 1개와 4개는 무조건 승리하는 경우이다. 하지만 2개는 무조건 패배한다. 항상 이 사람은 완벽하게 게임을하므로 무조건 상대가 패배할 수 있게 2개를 만들 수 있도록 3개를 가져갈 것이다. 그럼 2개는 무조건 패배하는 경우의 수이므로 이 사람은 무조건 승리하게 될 것이다.

 

6개의 경우에도 2개 3개 5개를 만들 수 있으며 항상 상대를 패배하도록 할 수 있으므로 이 사람은 승리할 것이다.

 

만약 돌이 7개 있으면 어떠할까? 다음 차례로 넘길 수 있는 경우의 수는 3개 4개 6개이다. 앞서 구했듯이 현재 주어진 돌이 3개 4개 6개인 경우에는 무조건 승리할 수 있다. 그럼 그 말은 무엇일까? 돌이 7개 있을 경우에는 이 사람은 무조건 패배한다는 것이다.

 

따라서 동적계획법을 이용해 규칙을 찾아보자. dp[놓여져 있는 돌의 수] 라고 가정할 때 -1로 초기화 한뒤 1을 현재 차례의 사람이 승리하는 경우, 0을 현재 차례의 사람이 패배하는 경우라고 가정하자. 그럼 dp[1,3,4]는 1이 될 것이고 dp[2]는 0이 될 것이다. 그 후 5부터 적당히 원하는만큼 탐색을 해보자. dp[i]가 0일 조건은 무엇일까? i에서 갈 수 있는 i - 1, i - 3, i - 4가 모두 dp의 배열 값이 1일 경우 상대를 승리시킬 수 밖에 없으므로 돌이 i 개 있을 때에 그사람이 패배하므로 0이 될 것이다. 반대로 하나라도 상대를 패배시킬 수 있는 루트가 존재한다면 승리할 수 있으므로 1이 된다.

 

 

따라서 다음과 같은 코드로 적당히 돌이 1 ~ 100개로 시작했을 때 누가 승리하는지 확인해 보았다.

 

그에 대한 결과가 이것이다.

규칙이 보이는가? 잘 찾아보면 CY가 이기는 경우는 7로 나눠떨어지는 경우와 나눈 나머지가 2인 경우라는 것을 알 수 있다. 결론적으로 정답 코드를 굉장히 간단하게 짤 수 있다.

 

아래는 소스 코드이다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  ll N;
  cin >> N;
  if(N % 7 == 0 || N % 7 == 2) {
    cout << "CY" << endl;
  }
  else {
    cout << "SK" << endl;
  }
}