[백준/JAVA] 1309번: 동물원

🔺 문제

1309번: 동물원

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MOD = 9901;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        // dp[i][j] : i번째 줄 j번째 칸에 동물을 놓을 수 있는 경우의 수
        long[][] dp = new long[N + 1][3];
        Arrays.fill(dp[1], 1);
        
        for(int i = 2 ; i <= N ; i++) {
            dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % MOD;    // j = 0 : 동물 없음
            dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % MOD;                 // j = 1 : 왼쪽 칸에 동물 있음
            dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % MOD;                 // j = 2 : 오른쪽 칸에 동물 있음
        }
        
        long ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD;
        System.out.println(ans);
    }
}

✅ 해결 아이디어
✔ DP
● dp[i][j] : i번째 줄 j번째 칸에 동물을 놓을 수 있는 경우의 수

 

• dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] : 이번 방에는 동물을 넣지 않으므로, 이전 방에서 동물이 어디 들어있든 OK

• dp[i][1]  = dp[i-1][0] + dp[i-1][2] : 이번 행의 왼쪽에 있는 경우, 이전 방에는 오른쪽에 들어있거나 없는 경우만 가능

• dp[i][2] = dp[i-1][0] + dp[i-1][1] : 이번 행의 오른쪽에 있는 경우, 이전 방에는 왼쪽에 들어있거나 없는 경우만 가능

 

 

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

2차원 배열 사용해야하는 건 알았는데.....

DP 식을 구하지 못 했다고 합니다,,,,,하하하ㅏ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[BOJ] 백준 1309번 : 동물원 (JAVA)

[백준 - 1309번] 동물원 - 자바(JAVA) 정리 및 해설

 

[알고리즘] - 백준 1309번 : 동물원 (JAVA)