백준 1309번: 동물원

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

 

2개의 열과 N개의 행으로 이루어진 공간에 가로, 세로로 붙어있지 않게 사자를 배치하는 모든 경우의 수를 구하는 문제이다.

dp로 경우의 수를 누적하며, N개의 열과 그 열의 상태에 해당하는 00, 10, 01을 열로 두어 상태 별 경우의 수를 누적한다.

 

dp[i][0] 는 1열, 2열 모두 배치하지 않으므로, 이전 행의 모든 경우의 수를 더한 값이다.. dp[i][1]은 왼쪽에 배치하므로 이전 행의 아무것도 배치하지 않거나 오른쪽에만 배치한 경우에만 가능하므로 이 둘의 경우의 수를 더한 값이다. dp[i][2]는 오른쪽에 배치하므로 이전 행의 아무것도 배치하지 않거나 왼쪽에만 배치한 경우의 수를 더한 값이다.

for (int i = 1; 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;
}

 

 

결과 코드는 다음과 같다.

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

public class 동물원1309 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        br.close();
        long[][] dp = new long[n][3];
        dp[0][0] = 1;
        dp[0][1] = 1;
        dp[0][2] = 1;
        for (int i = 1; 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.print((dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2]) % 9901);
    }
}