#9656 : 돌 게임 2

 

9656번: 돌 게임 2

풀이방법

사용된 것:

다이나믹 프로그래밍(DP)

수학

 

DP로 풀 수도 있고, 수학적으로 증명하여 풀 수도 있는 문제이다.

아래는 수학적 증명을 통해 문제를 풀어낸 과정이다.

 

2022.04.04

어떻게 풀지 고민하던 중, 카테고리가 DP라는 것을 발견했다.

DP 문제의 풀이를 도저히 모르겠을 때 꿀팁이 있다.

펜과 종이를 꺼내서 첫 몇 개의 경우의 수를 직접 계산해 보는 것이다.

그럼 데이터의 규칙성이 눈에 띄게 된다. 이 규칙성을 이용해 점화식을 세우면 DP식 해결법을 찾아낼 수 있다.

DP는 노가다가 통한다는 점이 참 좋은 것 같다.

 

그래서 돌멩이 한 개의 경우부터 열 개의 경우까지를 종이에 써가며 체크해봤다.

돌멩이가 1, 3, 5, 7, 9개일 때는 창영이가, 2, 4, 6, 8, 10개일 때는 상근이가 이겼다.

 

긴가민가 하는 심정으로 돌멩이가 짝수일 때 상근이가, 홀수일 때 창영이가 이기는 것으로 판단하는 코드를 적어 제출해보았더니 정답이었다.

 

손으로 적어봐서 처음 몇 개 케이스에 대하여 이게 들어맞는다는 건 확인했지만,

수학적으로 왜 맞는지를 모르겠다... 뭔가... 뭔가 더 증명이 필요해! 게임 이론이라는 것을 살펴봐야 하나?

생활패턴을 되돌리기 위해 잠을 덜 자서 수학적인 사고가 안 된다. 오늘 푹 자고 내일 더 생각해봐야지.

 

 

 

 

2022.04.06

푹 자긴 했는데 망할 어제 오늘 연속으로 10시간 넘게 자서 그 전이나 지금이나 다를 게 없다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

일찍 자는 건 성공했는데 일찍 자놓고 늦게 일어나고 있다. 잠만보인가? 큰일이다. 내일은 반드시 일찍 일어날 것이다.

 

최상의 상태에서 이 문제를 연구해보고 싶어서 어제는 하루종일 다른 공부를 했는데...

상황이 이렇게 되니 오늘은 끝을 봐야겠다는 생각이 들었다.

 

한 10분 고민해보니 알 수 있었다. 알고 보니 굉장히 간단했다...

 

일단, 상근이 차례에 2개의 돌이 있으면 무조건 상근이가 이긴다.

그리고 상근이 차례에 4개의 돌이 있으면 무조건 상근이가 이긴다.

 

4개보다 많은 돌이 있다고 가정해보자.

 

1개 아니면 3개씩만 가져갈 수 있으므로,

나 한 번 너 한번 가져가고 나면 그 전보다 무조건 짝수 개의 돌이 줄어들어있다.

 

따라서,

최초에 있던 돌멩이가 짝수 개라면

절대로! 상근이 차례에 돌멩이가 홀수인 상황은 발생하지 않는다.

그리고 결국 최후의 상근이 차례에는 돌이 2개 혹은 4개 남는다.

 

반대로

최초에 있던 돌멩이가 홀수 개라면

절대로! 상근이 차례에 돌멩이가 짝수인 상황이 발생하지 않는다.

 

굉장히 간단한 논리였다.

 

코드

Java(2022.04.04)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		if(Integer.parseInt(br.readLine()) % 2 == 0) System.out.print("SK");
		else System.out.print("CY");
	}

}