[BOJ] 백준 9658번 돌 게임4 (Java)

#9658 돌 게임4

난이도 : 실버 1

유형 : DP

9658번: 돌 게임 4

▸ 문제

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

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

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

 

▸ 입력

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

▸ 출력

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

 

 

 

문제 풀이  

전형적인 상향식 Bottom-up풀이 문제이다. 규칙을 찾아내어 점화식을 설계해주면 된다.

 

돌 게임3 문제에서 약간 변형이 되었다. 아래의 문제를 풀었다면 이 문제도 쉽게 풀 수 있을 것이다.

[BOJ] 백준 9657번 돌 게임3 (JAVA) - DOT CODING

 

이는 마지막 돌을 가져가면 지는 게임으로 상근이가 무조건 지는 게임을 설계하면 된다.

 

이번에는 창영이를 기준으로 dp[i]=1일 때 창영이가 이긴다고 설정했다.

 

초기값은 다음과 같다.

dp[1] = 1, dp[2] =0, dp[3] =1

 

그 다음은 경우의 수를 따져봐야한다.

dp[4] =0

> dp[i-1] = dp[3] = 1   : 상근 3개 ->  창영 1개

> dp[i-3] = dp[1] = 1  : 상근 1개 -> 창영 3개

> 따라서, 상근이 이길 수 있는 경우가 1개 이상이라도 존재할 때 상근 승리

 

 

돌이 n개 남았을 때, n-1 또는 n-3 또는 n-4개가 남은 시점에서 상근이가 이길 수 있는 경우가 하나라도 존재할 때, dp값은 0이다.

if(dp[i-1] + dp[i-3] + dp[i-4]>0) {
	dp[i] =0;
}

 

Bottom-up 풀이 코드 

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[1001];
		
		dp[1] =1;
		dp[2] =0;
		dp[3] =1;
		
		for(int i=4; i<=n; i++) {
			if(dp[i-1] + dp[i-3] + dp[i-4]>0) {
				dp[i] =0;
			}else {
				dp[i] =1;
			}
			
		}
		if(dp[n] ==0) {
			System.out.println("SK");
		}else {
			System.out.println("CY");
		}
		
	}
}

 

 

Top-down 풀이 코드 

점화식을 도출해낸 후 top-down방식으로 재귀호출을 해보니 직관적이여서 이해가 더 잘된다.. 그리고 도저히 점화식이 생각안날 때는 top-down 하향식으로 풀이하다보면 해답이 나올 수도 있다는 것을 생각하자.

import java.io.*;
import java.util.Arrays;

public class Main {

	static int[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		dp = new int[1001];
		
		Arrays.fill(dp, -1);
		
		if(solve(n) ==0) {;
			System.out.println("SK");
		}else {
			System.out.println("CY");
		}
	}
	
	static int solve(int num) {
		if(num <= 0) return 0;
		if(dp[num]!=-1) return dp[num];
		
		int win = solve(num-1) + solve(num-3) + solve(num-4);
		if(win >0) {
			return dp[num] = 0;
		}else {
			return dp[num] = 1;
		}
		
		 
	}
}