[백준] 1309 동물원 - Dynamic Programming / Java

• 문제 링크

1309번: 동물원

 

• 풀이 과정

n칸 마다 두 개의 방이 존재하고, 사자들을 배치할 때 가로 또는 세로로 붙어서 배치할 수 없는 조건에 의하여

이전 칸에 사자를 배치하지 않는 경우을 제외하고 이전에 배치된 방에 따라 현재 방의 배치가 결정된다.

 

배치하는 경우의 수는 3가지로,

dp[n][0] 은 두 개의 방 모두 배치하지 않은 경우,

dp[n][1] 은 첫 번째 방에 배치한 경우,

dp[n][2] 은 두 번째 방에 배치한 경우를 나타낸다.

 

따라서 2차원 dp배열을 dp[n + 1][3] 의 크기로 생성하고,

dp[1][0] = dp[1][1] = dp[1][2] = 1 로 각각의 경우를 초기화한다.

 

현재 칸에 배치하지 않을 시 이전 칸에 3가지 경우가 모두 가능하므로

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] 으로 나타낼 수 있으며 각각 % 9901 을 수행한다.

 

이 후 모든 경우의 수의 합 dp[n][0] + dp[n][1] + dp[n][2] 에 % 9901 을 수행한 값을 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[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;
        }

        bw.write((dp[n][0] + dp[n][1] + dp[n][2]) % 9901 + "\n");
        bw.flush();
    }

}