[백준] 9655 - 돌 게임 (JAVA)

1. 소요시간 : 11분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 5
4. 문제 유형 : 수학 , 다이나믹 프로그래밍 , 게임 이론
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/9655
8. 푼 날짜 : 2023.03.19

1. 사용한 자료구조 & 알고리즘

딱히 이렇다할 건 사용하지 않았다. 굳이 분류하자면 '수학'인 것 같다.

2. 사고과정

우선 처음에 문제를 잘못 읽어서 1,2,3 중 하나를 가져갈 수 있다고 이해했다. 나는 베스킨라벤스 게임을 2명이서 할 때의 필승 전략법을 알고 있기에 이를 응용해보기로 했었다.
베스킨라빈스 게임은 2,6,10,14,18,22,26,30 을 마지막으로 말하는 사람이 무조건 이길 수 있다. 따라서 선공이 무조건 이긴다. 이를 활용해보려고 했는데 5분이 지나서야 2를 말할 수 없다는 것을 알았다.

그래서 고민을 좀 해보다가 각각의 경우의 수를 그려보기로 했다.

5까지 그려봤을 때 n이 홀수라면 상근이가 이기고
n이 짝수라면 창영이가 이김을 알았다.

3. 풀이과정

n이 홀수라면 SK를
n이 짝수라면 CY를 출력한다.

4. 소스코드

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

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

		int n=Integer.parseInt(br.readLine());
		
		if(n%2==0)
			System.out.println("CY");
		else
			System.out.println("SK");
		
		
		
		
		
	}
}

5. 결과

6. 회고

DP스럽게 풀진 않았다. 그런데 다른 사람의 풀이를 보니 이를 DP스럽게 푼 풀이도 있었다.
그 분도 이 쉬운 풀이를 알지만 DP의 사고력을 높이기 위해서 일부러 그렇게 푼건 아닐까 생각해본다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212