[Silver II] 돌 게임 4 - 9658

문제 링크

성능 요약

메모리: 14312 KB, 시간: 124 ms

분류

다이나믹 프로그래밍, 게임 이론

제출 일자

2024년 2월 14일 10:40:41

문제 설명

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

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

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

입력

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

출력

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

코드

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

public class Main {
	static int dp[] = new int[1001];
	public static void main(String[] args) throws IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		dp[1]=0; // 0 은 창영이 이긴다.
		dp[2]=1; // 1 은 상근이 이긴다.
		dp[3]=0;
		dp[4]=1;
		for(int i=5; i<=1000; i++) {
			if(dp[i-1]+dp[i-3]+dp[i-4]==3) {
				dp[i]=0;
			}
			else {
				dp[i]=1;
			}
		}
		if(dp[n]==1) {
			System.out.println("SK");
		}
		else {
			System.out.println("CY");
		}
	}
}