[DP 연습] BOJ_9655 돌 게임 (S5)

https://www.acmicpc.net/problem/9655

9655번: 돌 게임

첫번째는, 내 코드! DP 문제라고 하니까 메모이제이션도 쓰고 그래야 할 것 같은데 사실 DP도 메모이제이션도 문제이해도 제대로 잘 안되는 상황에서 꾸역꾸역 DP로 풀었는데 백준에서는 안돌아가는 불쌍한 내 코드.. 사실 DP를 흉내내려고 노력했으나, 점화식은 점화식대로, 출력부는 출력부대로 따로따로 돌아가는 따로국밥!

두번째는, https://dev-gorany.tistory.com/271 여기서 가져온 코드인데 백준에서도 잘 돌아간다! 사실 DP라고 해서, 메모이제이션을 사용한다고 해서, 거창한 걸 저장하지 않아도 되는데 그게 잘 안되는 것 같다.. 가져온 솔루션에서만 봐도 짝수는 짝수대로, 홀수는 홀수대로 boolean 값만 저장해주고, N 값의 홀짝을 따져서 SK, CY를 출력해준다!

DP의 길은 역시 멀고도 험하다.. S5인데.. 은행 자소서를 쓰고 있기는 하지만, 다들 코테를 보니까 걱정이 이만저만이 아니다. 실버는 잘 풀어내야 할 것 같은데 코테 광탈할 것 같아서 뭐라도 해야할 것 같은데 너무 안일한 것 같아서 화가 난다! 추석연휴가 끝난 내일부터는 갓생 살아야지..

package algo0921;

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

// 돌 게임
public class BOJ_9655 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] games = new int[N+1];
		String winner = new String();
		
		// 기저조건 : 1 아니면 3 이니까 3까지
		games[0] = 0;
		games[1] = 1;
		games[2] = 1;
		games[3] = 2; 
		
		// 점화식
		for (int i = 4; i <= N; i++) {
			games[i] = games[i-1] + games[i-3];
		}

		// 출력
		if ((N-1)%2==0) {
			winner = "SK";
		} else winner = "CY";
		System.out.println(winner);
	}
}

package algo0921;

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

// 돌 게임
public class BOJ_9655_sol {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		boolean[] DP = new boolean[1001];
		
		DP[1] = true;
		DP[2] = false;
		
		for (int i = 3; i <= N; i++) {
			DP[i] = DP[i-2];
		}
		System.out.println(DP[N]? "SK" : "CY");
	}
}