[Java] 백준 9657번 : 돌 게임 3

문제

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

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

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

입력

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

출력

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

예제 입력 1

6

예제 출력 1

SK

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N;
	private static boolean []dp;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		dp=new boolean[N+1];
		
		dp[1]=true;
		if(N>=2) dp[2]=false;
		if(N>=3) dp[3]=true;
		if(N>=4) dp[4]=true;
		for(int i=5;i<=N;i++) {
			if(!dp[i-1] || !dp[i-3] || !dp[i-4]) dp[i]=true;	// 1, 3, 4개의 돌을 가져가기 이전 중 창영이가 이긴 경우가 존재하면, 그 다음은 반드시 상근이가 이기는 경우가 존재함
		}
		
		if(!dp[N]) System.out.println("CY");
		else System.out.println("SK");
	}

}

여기서 '완벽하게 게임을 했다'는 것은 '상근이가 이기도록 노력했다'는 것과 같은 의미입니다. 그러므로 상근이가 이기는 경우를 true로 하고, 창영이가 이기는 경우를 false로 하는 dp 배열을 만들어주었습니다.

 

N까지 반복문을 돌며 N-1, N-3, N-4번째에 각각 창영이가 이기는 경우가 한 가지라도 존재하면 N번째에는 상근이가 반드시 이길 수 있게 됩니다.