99클럽 코테 스터디 36일차 TIL + 돌 게임(백준)

오늘의 학습 키워드

   - 알고리즘

공부한 내용 본인의 언어로 정리하기

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

아이디어를 이용해 푸는 문제였다.

 

풀이 과정은 다음과 같다.

1. 돌이 1개라면 상근이가 무조건 이긴다.

2. 돌이 2개라면 창영이가 무조건 이긴다.

3. 돌이 3개라면 상근이가 무조건 이긴다.

4. 돌이 4개라면 상근이가 1개를 가져가면 3번으로, 3개를 가져가면 1번으로 가므로 창영이가 무조건 이긴다.

5. 돌이 5개라면 상근이가 1개를 가져가면 4번으로, 3개를 가져가면2번으로 가므로 상근이가 무조건 이긴다.

---

2n-1. 돌이 2n-1개라면 상근이가 무조건 이긴다

2n. 돌이 2n개라면 창영이가 무조건 이긴다.

 

라는 점화식으로 풀었다.

풀이는 다음과 같다.

import java.util.*;
import java.io.*;
public class Main
{

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String args[]) throws IOException
    {
        int n = Integer.parseInt(br.readLine());
        
        if (n % 2 == 0) System.out.println("CY");
        else System.out.println("SK");
    }
}