백준 9655 돌 게임 [Java]

풀이

상근이가 이기는 경우를 true, 지는 경우를 false!

n=1일 때, 상근이가 돌을 1개 가져가면 true
n=2일 때, 상근이가 돌을 1개 가져가고, 이어서 창영이가 마지막 1개를 가져가면 false
n=3일 때, 상근이가 돌을 3개 가져가면 true
n=4일 때, 상근이가 돌을 1개 가져가고 창영이가 3개를 가져가면 false. 혹은 상근이가 돌을 1개 가져가고 창영이가 1개, 상근이 1개를 가져가면 창영이가 마지막 1개를 가져간다.

★풀이1

n이 짝수면 (1,1), (1,3), (3,1), (3,3) 각각의 경우로 나누었을 때 나누어 떨어지기 때문에 창영이가 마지막 돌을 가져갈 수 밖에 없다.
반대로 n이 홀수이면, 마지막에는 1개 혹은 3개가 남으므로 상근이가 이긴다.

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

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());

		if(n%2 != 0) System.out.println("SK");
		else System.out.println("CY");

	}

}

★풀이2 DP를 이용한 풀이

dp[1] = true
dp[2] = false
dp[3] = true
dp[4]의 경우, dp[3]까지 간 후 마지막 남은 1개의 돌을 창영이가 가지고 가므로 false
dp[5]의 경우, dp[4]까지 간 후 마지막 남은 1개의 돌을 상근이가 가지고 가므로 true
.
.
.
따라서 n=4이상 부터는 dp[i] = !dp[i-1]이다

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

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());
		boolean [] dp = new boolean[n+1];
		
		dp[1] = true;  //상근이가 이김
		if(n > 1) {
			dp[2] = false;  //상근이가 짐
		}
		
		for(int i=3; i<=n; i++)
			dp[i] = !dp[i-1];
		
		if(dp[n]) System.out.println("SK");
		else System.out.println("CY");
    }
}

2023-03-08