BOJ_9655_돌게임 (Java)

[Silver V] 돌 게임 - 9655

문제 링크

성능 요약

메모리: 14304 KB, 시간: 104 ms

분류

다이나믹 프로그래밍, 게임 이론, 수학

제출 일자

2024년 10월 2일 09:28:31

문제 설명

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

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

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

입력

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

출력

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

문제 풀이

애드혹 문제라고 생각됐다. DP로도 풀 순 있지만 문제 답의 규칙성이 보여 그냥 규칙성으로 풀었다.DP로 푼다면 N번째에 N-1상태와 N-3상태를 보고 거기서 끝낼 수 있다면 승리함을 보여주면 될 것 같다.

게임의 답을 구하는 규칙성은 1대 or 3개를 살 수 있으므로 홀수개만 사고있음에 집중했다 (1~3개중 사는게 아니다) 그래서 남은 개수가 1개, 즉 홀수개가 남았다면 그 사람이 승리한다고 생각했고 나머지는 1혹은3이라 처음엔 1, 2, 3, 4 4가지로 나눠 1,3 / 2,4 처럼 하려했지만 나머지가 0, 1인걸로 해서 더 짧고 직관적으로 구현했다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		// br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		/*
		 * 완벽하게 게임 시 남은 개수로 승리조건 분석
		 * 1개 : 시작하는 사람 승 
		 * 2개 : 두번쨰 사람 승 
		 * 3개 : 시작하는 사람 승 
		 * 4개 : 두번째 사람 
		 * 5개 : 시작하는 사람 
		 * 즉 서로 홀수개밖에 사지 못하므로 홀수개가 남으면 시작하는사람 승, 짝수개가 남으면 두번째 사람 승이다  
		 */
		
		int N = Integer.parseInt(br.readLine());
		
		if(N %2 == 1) bw.write("SK");
		else bw.write("CY");
		
		bw.flush();
		bw.close();
		br.close();
	}
}