문제

---

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

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

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

입력

---

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

출력

---

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

문제풀이 1 (Java)

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    // SK부터 게임 시작한다고 가정했을때의 상황
    // 1. 돌이 1개가 남은 경우: 1개를 가져감 -> SK
    // 2. 돌이 2개가 남은 경우: 1개를 가져감 -> CY
    // 3. 돌이 3개가 남은 경우: 1개를 가져감 -> 2의 반대와 같음 / 3개를 가져감 -> SK
    // 4. 돌이 4개가 남은 경우: 1개를 가져감 -> 3의 반대와 같음 / 3개를 가져감 -> 1의 반대와 같음
    // 5. 돌이 5개가 남은 경우: 1개를 가져감 -> 4의 반대와 같음 / 3개를 가져감 -> 2의 반대와 같음
    // 6. 돌이 6개가 남은 경우: 1개를 가져감 -> 5의 반대와 같음 / 3개를 가져감 -> 3의 반대와 같음
    // 7. 돌이 7개가 남은 경우: 1개를 가져감 -> ...
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(n % 2 == 0 ? "CY" : "SK");

        bw.flush();
        bw.close();

    }

}

문제풀이 2 (Java)

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

    // 인덱스: 남아있는 돌의 갯수
    // 값: 게임 결과 ("SK" 또는 "CY")
    static String bottom_up_dp[] = new String[1001];
    static String top_down_dp[] = new String[1001];

    // bottom-up 으로 dp 채우고, 돌의 갯수가 n일때의 결과를 리턴
    public static String game_bu(int n) {
        // 초기 상태 저장
        bottom_up_dp[1] = "SK";
        bottom_up_dp[2] = "CY";
        bottom_up_dp[3] = "SK";

        for(int i = 4; i <= n; i++) {
            if(bottom_up_dp[i-1].equals("SK") || bottom_up_dp[i-3].equals("SK")) {
                bottom_up_dp[i] = "CY";
            } else {
                bottom_up_dp[i] = "SK";
            }
        }

        return bottom_up_dp[n];
    }

    // top-down 으로 dp 채우고, 돌의 갯수가 n일때의 결과를 리턴 (recursive)
    public static String game_td(int n) {
        // 초기 상태 조건 설정
        if(n == 1 || n == 3) {
            top_down_dp[n] = "SK";
            return top_down_dp[n];
        }

        // dp에 저장되어 있는 값이라면 바로 반환
        if(!top_down_dp[n].equals("")) {
            return top_down_dp[n];
        }

        // recursive 사용
        if(game_td(n-1).equals("SK") || game_td(n-3).equals("SK")) {
            top_down_dp[n] = "CY";
        } else {
            top_down_dp[n] = "SK";
        }

        return top_down_dp[n];
    }

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Arrays.fill(bottom_up_dp, "");
        Arrays.fill(top_down_dp, "");

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        bw.write(game_bu(n));
        bw.newLine();
        bw.write(game_td(n));

        bw.flush();
        bw.close();

    }

}

문제풀이 1번은 단순 홀짝 조건식으로, 2번은 dp를 bottom-up, top-down 모두 구현했다.
(실제로 제출할때는 bw.write 부분을 잘 주석처리하면 된다.)

반복문만 있는 bottom-up 방식이 재귀를 쓰는 top-down 보다는 약간 빠르다. 004ms 정도..