[BOJ 9661] 돌 게임 7

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

9661번: 돌 게임 7

 

- 문제 요약

 

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. (1 ≤ N ≤ 1,000,000,000,000)

상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 4x개만큼 가져갈 수 있다.

즉, 가능한 개수는 1, 4, 16, 64, ...개 이다.

4x개만큼 돌을 가져갈 수 있는 방법이 없는 사람이 게임을 지게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오.

게임은 상근이가 먼저 시작한다.

 

 

- 알고리즘 정리

 

돌 게임에서는 번갈아가며 돌을 4x개만큼 가져갈 수 있습니다.

DP로 푸는 방법도 있겠지만, 저는 그냥 시뮬레이션으로 규칙성을 찾아 풀어봤습니다. 

돌의 개수를 N이라고 할 때, N=1 -> SK, N=2 -> CY, N=3 -> SK, N=4 -> SK, N=5 -> CY와 같은 패턴을 보였습니다.

=> N mod 5가 0 또는 2라면 CY, 아니면 SK

 

 

- 코드 작성

 

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

typedef long long ll;
ll n;

int main(){
    cin>>n;
    n=n%5; 
    if(n==0||n==2){
        cout<<"CY"; 
    }
    else{
        cout<<"SK"; 
    }
}

코드 제출 결과