[BOJ/백준] 9657 돌 게임 3 (S3)

문제

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

풀이

돌이 N개가 있고 상근이가 먼저 게임을 시작하며 돌을 1개, 3개, 또는 4개를 가져갈 수 있을 때 마지막 돌을 가져가는 사람이 이기는 게임이다. 문제에 '완벽하게' 라는 조건이 붙었기 때문에 상근이가 이기는 쪽으로 게임을 해야 한다.

 

돌의 개수 별로 돌을 가져간 횟수?를 저장하는 배열 arr을 생성한다.

돌을 한 번에 4개를 가져갈 수 있기 때문에 N=1 ~ N=4까지는 고정 값을 넣어주었다.

• N = 1 : 상근이가 돌 1개를 가져가면 게임이 끝난다. → 상근 Win : arr[1] = 1
• N = 2 : 상근이가 돌 1개를 가져가고 창영이가 돌 1개를 가져가면 게임이 끝난다. → 창영 Win : arr[2]  = 2
• N = 3 : 상근이가 돌 3개를 가져가면 게임이 끝난다. → 상근 Win : arr[3] = 1
• N = 4 : 상근이가 돌 4개를 가져가면 게임이 끝난다. → 상근 Win : arr[4] =  1

N = 5 부터는 for 루프를 돌려 Bottom-up 형식으로 밑에서부터 배열을 채워 나간다. arr[n] = 1이면 상근이가 이기고, arr[n] = 2면 창영이가 이긴다.

Code

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int arr[] = new int [1001];

        arr[1] = 1;  // sk
        arr[2] = 2;  // cy
        arr[3] = 1;  // sk
        arr[4] = 1;  // sk
        for (int i = 5; i <= n; i++) {
            if (arr[i-1] % 2 == 0 || arr[i-3] % 2 == 0 || arr[i-4] % 2 == 0) {
                arr[i] = 1;
            } else {
                arr[i] = 2;
            }
        }

        if (arr[n] % 2 == 0) {
            bw.write("CY");
        } else {
            bw.write("SK");
        }
        bw.flush();
        bw.close();
    }
}