백준 1309 - 동물원

경우의 수를 구하는 DP로 생각을 했다.

 

테이블을 [N][3] 크기로 만들고

 

[N][0] 이번 라인에 없는 경우

[N][1] 이번 라인은 왼쪽

[N][2] 이번 라인은 오른쪽

 

으로 생각 하고 문제를 품.

 

한방에 해결.

 

import java.util.Scanner;
 
public class Main {
 
    static int[][] caseArr;
    static int na = 9901;
    static int result;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
 
        caseArr = new int[N][3];
 
        for (int i = 0; i < caseArr[0].length; i++) {
            caseArr[0][i] = 1;
        }
 
        for (int i = 1; i < caseArr.length; i++) {
            for (int j = 0; j < caseArr[i].length; j++) {
                // 하나도 없는 경우
                caseArr[i][0] = (caseArr[i - 1][0] + caseArr[i - 1][1] + caseArr[i - 1][2]) % na;
                // 왼쪽에 있는 경우
                caseArr[i][1] = (caseArr[i - 1][0] + caseArr[i - 1][2]) % na;
                // 오른쪽에 있는 경우
                caseArr[i][2] = (caseArr[i - 1][0] + caseArr[i - 1][1]) % na;
            }
        }
 
        result = ((caseArr[N - 1][0] + caseArr[N - 1][1] + caseArr[N - 1][2]) % na);
 
        System.out.println(result);
 
    }
 
}
 

하고 나서 보니 답에 규칙이 또 있는거 같아 줄여보았다.

 

import java.util.Scanner;
 
public class Main {
 
    static int[] caseArr;
    static int na = 9901;
    static int result;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
 
        caseArr = new int[N + 1];
 
        caseArr[0] = 1;
 
        caseArr[1] = 3;
 
        for (int i = 2; i < caseArr.length; i++) {
            caseArr[i] = (caseArr[i-2] + (caseArr[i-1]*2)) % na;
        }
        
        System.out.println(caseArr[N]);
 
    }
 
}
 

메모리와 시간이 줄었음. 

 

역시 한방에 해결