[알고리즘][DP][2913] 이친수

[알고리즘][DP][2913] 이친수

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

[풀이]

• 규칙을 코드로 표현하다가 길어져서 점화식을 구해서 코드로 구현했다.
• 다양한 설명이 많은데 이에 대해선 다시 한번 해봐야겠다.
• arr[1] = 1
• arr[2] = 1
• arr[3] = 2
• arr[4] = 3
• arr[5] = 5
• arr[6] = 8
• ..
• arr[n] = arr[n-1] + arr[n-2] 라는 식이 도출 가능하다.
• 유의해야 할 점은 arr[1]과 arr[2]가 모두 1 이라는 점!

[코드]

package algorithm_basic;
 
import java.util.Scanner;
import java.math.*;
 
public class q_2193 {
    
    public static void main(String[] args)   {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(); //n자리
        
        System.out.println(calc(n));
        
    }
    public static long calc(int n) {
        long[] arr = new long[n+1];
        
        arr[1]=1;
        if(n>=2) {
            arr[2]=1;
        }
        
        for(int i=3;i<=n;i++) {
            arr[i] = arr[i-2]+arr[i-1];
        }
        return arr[n];
    }
}