백준알고리즘 1309번 동물원

백준알고리즘

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

기저 사례를 잘 새워야한다

D[i] = D[i-1] * 2 + D[i-2]임을 알 수있다. 네모를 하나하나 한땀한땀 그려서 규칙을 찾아보자.

import java.util.Scanner;

public class Main {
    static int[] inputArray = null;
    static int[] memoArray = null;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int value = Integer.parseInt(scan.nextLine().trim());
        
        long memo[] = new long[100000+1];
        memo[0] = 1;
        memo[1] = 3;
        
        for(int i = 2; i <= value; i++) {
            memo[i] = ((memo[i-1] * 2) + memo[i-2]) % 9901;
        }
        
        System.out.println(memo[value]);
    }
}