[백준] 1309 동물원

문제보기

1. 수학으로 풀기

   천천히 몇개 보다보면 규칙이 나온다. i번째 항은 i-1번째항*2 + i-2번째항+2 로 이뤄진다

   DP로 하는건 나중에 올리겠음 ㅠㅠ

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

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());

    long[] d = new long[n+1];

    // 초기값
    d[1] = 2;
    
    // n == 1 이면 걍 빨리 끝내자
    if(n == 1){
      System.out.println(3);
      return;
    }
    d[2] = 6;

    for(int i = 3 ; i <= n ; i++ ){
      d[i] = d[i-1]*2 + d[i-2]+2;
      d[i] %= 9901;

    }
    System.out.println((d[n] + 1)%9901);
  }
}