[백준/1309] 동물원 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버1
출처 : 백준 - 동물원

🦧 문제 풀이 접근

맨 아래칸 중 왼쪽에 사자를 넣는 경우, 오른쪽에 사자를 넣는 경우, 둘 다 넣지 않는 경우를 생각해보자. 그 경우 dp[i] = dp[i-1]*2 + dp[i-2] 가 된다.

dp[i-1] => 왼쪽 혹은 오른쪽만 사자를 넣는 경우
dp[i-2] => 양쪽 모두 넣지 않는 경우

💻 code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[100_001];
        dp[0] = 1;
        dp[1] = 3;
        for(int i=2;i<100_001;i++) {
            dp[i] = (dp[i-1]*2 + dp[i-2]) % 9_901;
        }
        System.out.println(dp[N]);
    }
}

🥇 결과

🎓 느낀점

점화식을 빠르게 도출하면 쉽게 풀 수 있다.