[Java] 백준 9658번 돌 게임 4

다이나믹 프로그래밍으로 문제를 풀었습니다.

돌 개수에 따라 누가 승리하는지를 bottom up 방식으로 저장해주었습니다.

먼저 1, 2, 3, 4개의 경우 미리 계산을 하고 5부터 최대 입력값인 1000까지 계산을 해주었습니다.
현재 돌 개수 -1, -3, -4개일 때 모두 다 상근이가 이기는 경우 현재 돌의 개수 일 때 반드시 창영이가 승리합니다.
모두 이기는 경우만 창영이가 승리하는 이유는 상근이가 먼저 돌을 가져가기 때문에 지는 경우로 두지 않기 때문입니다.
그 외에는 상근이의 승리로 해주었습니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static int n;
	static int[] DP = new int[1001];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		DP[1] = 0;
		DP[2] = 1;
		DP[3] = 0;
		DP[4] = 1;
		for(int i=5; i<1001; ++i) {
			if((DP[i-1] & DP[i-3] & DP[i-4]) == 1) {
				DP[i] = 0;
			} else {
				DP[i] = 1;
			}
		}
		
		bw.write(DP[n]==1?"SK":"CY");
		bw.close();
	}
}