백준 9657 JAVA : 돌 게임 3

문제

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

9657번: 돌 게임 3

 

풀이 예상

이전 돌멩이의 개수를 보고 승리를 예측 하는 것 이라고 생각했고

돌을 1, 3, 4 개씩 가져갈 수 있기 때문에 지금 돌멩이의 개수에서 -1, -3, -4 부분을 보고 현재 돌멩이에서 누가 이기는지 예측하는 것 이라고 생각했다.

 

돌을 딱 맞춰가지 않아도 되는 줄 알고,, 헛다리 짚었었는데 ex) 2 라면 상근이가 3개나 4개 선택해서 가져가면 이기는줄..

돌 개수를 딱 맞춰가야 했었다.

 

N을 늘려가면서 누가 이기는지 표로 그려 봤을 때, 다음과 같은 규칙을 찾을 수 있었다.

i-1, i-3, i-4 부분 에서 창영이가 이긴다면 i 번째는 상근이가 무조건 이긴다. => 항상 최선을 다하기 때문에 이전타임에서 창영이가 이긴다면 상근이는 무조건 이기려고 하기 때문에

이 규칙을 코드로 작성하면 된다.

N	이기는 사람	이유
1	상근	처음에서 1개 선택
2	창영	상근 1개 선택 후 창영 1개 선택
3	상근	처음에서 3개 선택
4	상근	처음에서 4개 선택
5	상근	4, 2, 1 중 하나라도 창영이가 이기면 상근이가 무조건 이긴다.
6	상근	5, 3, 2 중 하나라도 창영이가 이기면 상근이가 무조건 이긴다.
7	창영	6, 4, 3 모두 상근이가 이기기 때문에 창영이가 이긴다.
8	상근	7, 5, 4 중 하나라도 창영이가 이기면 상근이가 무조건 이긴다.

 

 

풀이방법 (접근 방법 & 시간복잡도)

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

public class Main {
    static int N;
    static boolean[] isWin; //i개 돌이 남아있을 때 이길 수 있는지 -> true: 상근이가 이김, false: 창영이가 이김
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        isWin = new boolean[1001];
        isWin[1] = true;
        isWin[3] = true;
        isWin[4] = true;

        for (int i = 5; i <= N; i++) {
            //이전에 하나라도 상근이가 졌다면 지금은 상근이가 이긴다.
            //5 -> 상근, ----> 4, 2, 1 중 하나라도 창영이가 이기면 상근이가 무조건 이긴다.
            if(!isWin[i-1] || !isWin[i-3] || !isWin[i-4]) {
                isWin[i] = true;
            }
        }
        if(isWin[N]) {
            System.out.println("SK");
        }else {
            System.out.println("CY");
        }

    }
}

 

결과