[Java] 백준 9659번 : 돌 게임 5

문제

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

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

예제 입력 1

5

예제 출력 1

SK

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	private static BufferedReader br;
	
	private static long N;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		N=Long.parseLong(br.readLine());
		if(N%2==0) System.out.println("CY");
		else System.out.println("SK");
	}

}

돌 게임 4까지는 dp를 이용하여 문제 해결이 가능했습니다. 그러나 5번 문제는 N값의 범위가 int를 넘어가므로 해당 범위 크기의 배열을 만들 수 없게 됩니다. 따라서 짝수일 때 상근이가, 홀수일 때 창영이가 이긴다는 규칙을 이용하여 해결해주어야 합니다.