2022.03.20 85일차

백준 9655번 (돌 게임)

문제

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

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

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

나의 풀이

1. 경우의 수 생각해보기
   1개일 때 상근, 2개일 때 창영, 3개일 때 상근, 4개일 때 창영, ...
2. 짝수 창영, 홀수 상근

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

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

        int N = Integer.parseInt(br.readLine());

        String answer = N % 2 == 1 ? "SK" : "CY";

        System.out.println(answer);
    }
}

생각하기

• DP 형식으로 풀어보기

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

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

        int N = Integer.parseInt(br.readLine());

        dp = new int[N + 1];


        int answer = funcDP(N);

        if (answer == 1) {
            System.out.println("SK");
        } else {
            System.out.println("CY");
        }

    }

    static int funcDP(int N) {

        if (N == 1 || N == 3) {
            return dp[N] = 1;
        }

        if (N == 2) {
            return dp[N] = 0;
        }

        if (dp[N] > 0) {
            return dp[N];
        }

        return funcDP(N - 2);
    }
}