백준 9655번 돌 게임 JAVA

링크텍스트

설명

처음에는 그리디를 이용해 풀었는데 DP로도 풀이가 가능하다.
시간복잡도: O(N), 공간복잡도: O(1)

코드

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

class Main {
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int count = 0;

		int n = Integer.parseInt(br.readLine());

		while(n>0){
			
			if(n>=3) n-=3;
			else n--;
			count++;
		}

		System.out.println((count%2)==0 ? "CY" : "SK" ) ;

	}
}

DP 코드

import java.util.*;
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] = 2;
        dp[3] = 1;
        for (int i = 4; i <= n; i++) {
            dp[i] = Math.min(dp[i-1],dp[i-3]) + 1;
        }
        if (dp[n] % 2 == 0) {
            System.out.print("CY");
        } else {
            System.out.print("SK");
        }
    }
}