import java.util.Scanner;
public class ex1904 {
public static int[] dp = new int[1000001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
// -1 로 초기화
for(int i = 3; i < dp.length; i++) {
dp[i] = -1;
}
System.out.println(fibo(n));
}
public static int fibo(int n) {
// 계산되어있지 않는 부분만 호출 , 메모이제이션
// fibo(4)를 호출하게 되면 fibo(2)가 2번호출되는것을 1번만 호출하기 위함.
if(dp[n] == -1) {
dp[n] = (fibo(n - 1) + fibo((n - 2))) % 15746;
}
return dp[n];
}
}
이 문제는 쉬워보여도 굉장히 까다로운 문제다. 우선 n값의 범위는 100만 까지 주어진다.
그리고 하나 배운 점
이 문제의 규칙을 찾다보면 피보나치와 같은 규칙이라는 것을 쉽게 알 수 있다. 그래서 쉬워보였다.... 여기서 핵심은 메모이제이션이다. 예를 들어 fibo(4)를 호출한다고 하자. 그러면 fibo(3) + fibo(2)를 호출하게 되는데 fibo(3)은 또 다시 fibo(1)과 fibo(2)를 호출하게 되므로 fibo(2)를 2번 호출하게된다. 굉장히 비효율적이다. 그래서 조건을 걸어서 초기화되어있던 값이 아닌경우에는 fibo()를 호출하지 않는다.