[알고리즘] 9658. 돌 게임 4

0. 문제

 

 

9658번: 돌 게임 4

 

---

1. 문제 이해

 

2개의 돌을 뺄 수 없다는 조건 때문에 수학적 규칙을 찾기 어려웠다.

 

N=1000이고 제한시간은 1초다.

 

1초를 1억으로 가정하면 시간복잡도는 O(n^2)쯤이다.

 

모든 경우의 수를 다 구해서 풀면 O(n^3)이다.

 

DP로 풀어야 한다.

 

상근이가 이기는지 지는지 알아내는 방법은 다음과 같다.

 

1. 돌의 개수가 1 ~ 5까지는 비교적 쉽게 구할 수 있다.
2. 돌의 개수가 6일 때는 6에서 1, 3, 4개를 빼본다.
3. 6 - 1 = 5, 6 - 3 = 3 그리고 6 - 4 = 2에서 단 한 번이라도 상근이가 이기면 6에서도 상근이가 이긴다. (= 모든 경우에서 창영이가 져야 한다.)
4. 돌의 개수가 7, 8, …, N-1, N에 대해서도 반복한다.

 

큰 문제를 작은 문제로 나누고 작은 문제의 결괏값을 큰 문제를 풀 때 사용한다.

 

---

2. 제출

import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
    static boolean[][] arr = new boolean[1001][3];
    static final int[] dn = {1,3,4};

    public static void init(){
        for(int i=0; i<1001; i++){
            for(int j=0; j<3; j++){
                arr[i][j] = false;
            }
        }
        // n=1
        //arr[1][0] = false;
        //arr[1][1] = false;
        //arr[1][2] = false;
        // n=2
        arr[2][0] = true;
        //arr[2][1] = false;
        //arr[2][2] = false;
        // n=3
        //arr[3][0] = false;
        //arr[3][1] = false;
        //arr[3][2] = false;
        // n=4
        arr[4][0] = true;
        arr[4][1] = true;
        //arr[4][2] = false;
        // n=5
        //arr[5][0] = false;
        //arr[5][1] = false;
        arr[5][2] = true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        init();
        int n = Integer.parseInt(st.nextToken());
        for(int i=6; i<=n; i++){
            for(int j=0; j<3; j++){
                int tmp = dn[j];
                if(arr[i-tmp][0]||arr[i-tmp][1]||arr[i-tmp][2]){
                    continue;
                }
                arr[i][j] = true;
            }
        }
        String ret = arr[n][0] || arr[n][1] || arr[n][2] ? "SK" : "CY";
        System.out.println(ret);
    }
    br.close();
}

규칙을 찾으려고 시도하면서 너무 많은 시간을 썼다.

 

듣기에는 18부터 규칙이 보이기 시작한다는데… 잘 모르겠다.

 

for(int i=6; i<=n; i++){
        for(int j=0; j<3; j++){
            int tmp = dn[j];
            if(arr[i-tmp][0]||arr[i-tmp][1]||arr[i-tmp][2]){
                continue;
            }
            arr[i][j] = true;
        }
    }

또 위의 i, j, tmp의 위치를 혼동해서 시간을 많이 낭비했다.

 

급해도 손코딩은 깔끔하게 마무리하고 코딩을 시작하자.

 

---