[백준] 9659 돌 게임 5 - 동적계획법(DP, Dynamic Programming) + 게임이론(Game Theory) + 수학(Math) JAVA

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

코드설명

동적계획법(DP, Dynamic Programming) + 게임이론(Game Theory) + 수학(Math) 입니다.

 

이 문제의 경우, 일반적인 동적계획법으로는 적용이 불가합니다.

이유는 N이 1조입니다. 10^12 입니다.

 

그렇기에, 배열의 Size는 오직 int형(21억)개만 가능하기에, 동적계획법 적용이 어렵습니다. 

 

문제의 특성을 파악해서 풀어야하는 문제였습니다.

 

직접 N=1, N=2, N=3... 을 하다보면 규칙을 찾을 수 있습니다.

1. 만약 돌이 홀수개라면, 상근이가 이깁니다.

2. 만약 돌이 짝수개라면, 창영이가 이깁니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
    private static long N, T, M;
    private static int answer = 0;
    private static int[][] cache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Long.parseLong(st.nextToken());
		System.out.println(N % 2 == 1 ? "SK" : "CY");
	}
    
}