[백준]1309 동물원

감이 잡힐락 말락 .. 알 것 같다가도 모르겠고 .. 우선 메모리초과로 실패했지만 내 접근법은 이랬다.

package baekjoon;

import java.util.Arrays;
import java.util.Scanner;

public class Main_1309 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();       // 사자 우리의 크기
        int[][] dp = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            dp[i][0] = 1;           // 한마리도 배치하지 않을 경우 = 1
            dp[i][1] = (2*N);       // 한마리씩 배치할 경우 가로X세로
            dp[i][N] = 2;           // 우리가 꽉 찬 지그재그 배치 = 2
            for (int j = 2; j < i; j++) {
                //System.out.println("dp[" + (i - 1) + "][" + (j) + "]");
                dp[i][j] = (2 * (2 * (N - 1)-1)) + dp[i - 1][j];
                //System.out.println((2 * (2 * (N - 1)-1)) + " + " + dp[i - 1][j]);
            }
        }
        int sum = Arrays.stream(dp[N]).sum();
        System.out.println(sum%9901);

    }
}

완져니 모르겠어서 결국 풀이의 도움 ...
2차원 배열에
N행과 사자가 없을때, 왼쪽에 있을때, 오른쪽에 있을 때로 나눠 값을 저장해야했다.

dp[N][0] = 사자가 어디에도 없을때
dp[N][1] = 사자가 N행의 왼쪽에 있을 때 (N-1행에서 사자가 오른쪽에 있거나 있지 않아야함)
dp[N][2] = 사자가 N행의 오른쪽에 있을 때 (N-1행에서 사자가 왼쪽에 있거나 있지 않아야함)

package baekjoon;

import java.util.Arrays;
import java.util.Scanner;

public class Main_1309 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();       // 사자 우리의 크기
        int[][] dp = new int[N+1][3];

        dp[1][0] = 1;
        dp[1][1] = 1;
        dp[1][2] = 1;

        for(int i=2;i<=N;i++){
            dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
            dp[i][1]=dp[i-1][2]+dp[i-1][0];
            dp[i][2]=dp[i-1][1]+dp[i-1][0];

            dp[i][0] %= 9901;
            dp[i][1] %= 9901;
            dp[i][2] %= 9901;
        }
        System.out.println(Arrays.stream(dp[N]).sum()%9901);

    }
}

..정말 어렵다 미쳐버려