백준 [1309] 동물원 (JAVA)

문제

풀이

사자는 가로 또는 세로로 함께 배치할 수 없다. 즉, 사자가 해당 칸에 있으면 상하좌우로 다른 사자를 배치할 수 없다.

 

dp 배열을 두고 각 칸에 다음과 같이 배치하는 경우가 있다.

1. 배치하지 않는 경우 (j = 0)
2. 첫 번째 칸에 배치하는 경우 (j = 1)
3. 두 번째 칸에 배치하는 경우 (j = 2)

1 번째 줄에 사자를 배치하지 않는 경우는 1개 dp[1][0] = 1;

1 번째 줄의 1번째 칸에 사자를 놓는 경우는 1개 dp[1][1] = 1;

1 번째 줄에 2번째 칸에 사자를 놓는 경우는 1개 dp[1][2] = 1;

 

2 번째 줄에 사자를 배치하지 않는 경우는 이전 1번째에서 3가지 경우를 모두 합친 경우의 수가 된다.

따라서 dp[2][0] = dp[1][0] + dp[1][1] + dp[1][2];

 

2 번째 줄의 1번째 칸에 사자를 놓는 경우는 이전에 1번째 칸에 두는 경우가 붙어 있도록 배치하는 경우라서 포함하면 안된다.

따라서 dp[2][1] = dp[1][0]  + dp[1][2];

 

2 번째 줄의 2번째 칸에 사자를 놓는 경우는 이전에 2번째 칸에 두는 경우가 붙어 있도록 배치하는 경우라서 포함하면 안된다.

따라서 dp[2][1] = dp[1][0]  + dp[1][1];

 

이 부분을 일반화하여 표현하면

 

dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];

dp[i][1] = dp[i - 1][0] + dp[i - 1][2];

dp[i][2] = dp[i - 1][0] + dp[i - 1][1];

 

N까지 구하면 N번째의 모든 경우의 수는 이전까지의 배치하지 않은 경우와 1번째칸, 2번째칸에 배치하는 경우의 수를 고려한 모든 경우의 수가 된다.

 

int 범위로 두어도 범위를 초과하지 않아서 그대로 사용하였다.

dp 값들을 구할 때와 마지막 답을 구할 때 mod 연산을 해주었다.

 

 

정답코드

package com.baekjoon.p1309;

import java.util.*;

public class Main {
    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] = dp[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]) % 9901;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
        }

        System.out.println((dp[N][0] + dp[N][1] + dp[N][2]) % 9901);
        sc.close();
    }
}