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

#9657 돌 게임3

난이도 : 실버 3

유형 : DP/ 게임 이론

9657번: 돌 게임 3

▸ 문제

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

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

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

 

▸ 입력

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

 

▸ 출력

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

 

 

 

문제 풀이 

돌맹이 n개를 1,3,4개를 가져갈 수 있고 마지막으로 가져간 사람이 이기는 게임이다. 처음에는 단순하게 규칙을 찾아 풀었지만 dp로 분류된 문제이니 dp로도 풀어야겠다 싶어서 다시 풀었다. 

 

규칙 찾기 문제로, 경우의 수를 몇 번 계산해보면 금방 규칙을 찾을 수 있다.

상근이는 7을 주기로 패/승/패/승/승/승/승 의 경우의 수가 나온다.

 

DP 풀이

상근이를 기준으로 dp[i] = 1 이면 상근이 이긴다고 설정했다.

 

돌이 1개, 3개, 4개가 있으면 무조건 상근이가 승리하고 2개일 경우 조합이 (1,1)밖에 안되기 때문에 무조건 상근이가 패배한다.

 

그래서 초기값은 다음과 같다.

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

 

위의 초기값을 토대로 점화식을 설계하면 된다. 이 게임은 상근이가 먼저 시작하므로 주도권은 상근이한테 있다.

 

예) 6개의 돌로 시작하는경우

1  -> dp[5] = 1 (dp[5]는 dp[4], dp[2], dp[1] 중 이기는 경우 1개라도 존재하므로 1)

3  -> dp[3] = 1

4  -> dp[2] = 0

☛ 상근이가 먼저 뽑아서 두 번째로 뽑는 창영이가 지는 경우의 수가 존재하면 무조건 상근이가 그걸 계산해서 이긴다고 보면 된다.

(4개를 잡으면 상근이 승리 4(SK)-> 1 (CY)-> 1(SK) )

 

그럼 반대로 무조건 상근이가 지는 경우는 언제일까?

 

예) 7개의 돌로 시작하는 경우

1  -> dp[6] = 1

3  -> dp[4] = 1

4  -> dp[3] = 1

 

☛ 다음과 같이 상근이가 먼저 뽑은 다음 두 번째로 뽑는 창영이가 지는 경우의 수가 없을 때이다. 위의 경우랑은 역으로 무엇을 뽑든 지는 경우가 있다. 

 

그래서 dp[i-1] + dp[i-3] + dp[i-4] == 3이면, 다음에 상근이는 무조건 지기때문에 dp[i]=0으로 값을 주고

나머지는 다 1로 이기는 경우의 수가 존재하기 때문에 이런식으로 메모이제이션을 해나가면 된다.

 

 

풀이 코드 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		// if 1 : SK win
		//    0 : CY win  
		int[] dp = new int[n+1];
		dp[1] =1;
		dp[2] =0;
		dp[3] =1;
		dp[4] =1;
		
		for(int i=5; i<n+1; i++) {
			// 1,3,4 == 합 3이면 뭐를 넣어도 다음 사람이 이김 
			if(dp[i-1] + dp[i-3] + dp[i-4] <3) {
				dp[i] =1;
			}else {
				dp[i] =0;
			}
		}
		
		if(dp[n] ==1) {
			System.out.println("SK");
		}else {
			System.out.println("CY");
		}
		
		
		
//		규칙 풀이 
//		int d = n%7;
//		
//		System.out.println(d);
//		
//		switch(d) {
//			case 0: case 2:
//				System.out.println("CY");
//				break;
//			default:
//				System.out.println("SK");
//				break;
//		}
	}
	
}