[BOJ] 9657 : 돌 게임3(Java)

문제

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

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

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

입력

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

출력

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

---

💡풀이

각 돌의 개수에 대해 승리자를 담을 boolean형 배열을 하나 생성하고 상근이가 이기면 true, 창영이가 이기면 false가 입력된다. 

돌의 개수 1부터 4까지는 각각 상근, 창영, 상근, 상근이 승리자가 된다. 이 후(5개)부터는 돌 1개, 3개, 4개를 뺐을 때, 만약 이 값이 false(창영이가 이기는 경우)라면 해당 돌은 상근이가 이기는 경우이다. 이러한 상황이 아니라면, 창영이가 승리하는 경우이다. 

 

전체적인 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q9657 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        boolean[] dp = new boolean[1001];
        dp[1] = true;
        dp[2] = false;
        dp[3] = true;
        dp[4] = true;
        for(int i=5;i<=N;++i){
            dp[i]=false;
            if(!dp[i-1]||!dp[i-3]||!dp[i-4])
                dp[i] = true;
        }
        System.out.println(dp[N] ? "SK" : "CY");
    }

}