백준 2193번 이친수

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

요약.
맨처음 숫자는 1 고정, 1은 연속해서 사용불가
경우의 수를 생각해서 한번 인덱스를 나열해 보다보니 자주 보았던 규칙이 보였다.

1, 1, 2, 3, 5, 8, 13

3항부터 이전 두항의 합인 피보나치 수열이 되는 것을 확인할 수 있었고 피보나치 수열이라는 것만 알게되면 쉬운문제였다.

import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    
    int dp[] = new int[91];
    dp[1] =1; 
    dp[2] =1; 
    for(int i=3; i<dp.length; i++){
      dp[i] = dp[i-2] + dp[i-1];
    }

    System.out.println(dp[n]);
  }
}