[백준] 동물원

 

 

참고 : www.acmicpc.net/problem/1309

1309번: 동물원

 

- dp 문제

- dp[i] : dp[i-1]* 2 + dp[i-2] 의 공식이 성립 (왜 성립하는 지 알아보고 수정할 것)

- 아주 좋은 링크 : m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220784781196&proxyReferer=https:%2F%2Fwww.google.com%2F

 

import java.io.*;
import java.util.*;

public class Solution {

    private static int n;
    private static int[] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dp = new int[n+2];
        dp[1] = 3;
        dp[2] = 7;
        for(int i=3;i<=n;i++) {
            dp[i] = (2*dp[i-1] + dp[i-2]) % 9901;
        }
        System.out.println(dp[n] % 9901);
    }
}