코드트리 [자바 java] 피보나치 수

https://www.codetree.ai/missions/2/problems/fibonacci-number?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

수가 주어지면 해당 수 번째의 피보나치수를 구하는 문제이다.

 

첫번째와 두번째 피보나치 수는 1이므로 이들이 주어지면 바로 1을 출력하게 하였고

나머지 수들은 주어진 수 만큼 dp배열을 만들고, dp[0],dp[1]에 1을 넣은 후 2부터 차례대로 전과 전전 dp값을 더한 값을 넣었다. 위 과정이 다 실행되면, dp에 있는 제일 끝 값을 출력하도록 했다.

 

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



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());
        
        int[] dp = new int[n];

        if(n == 1 || n ==2) System.out.println(1);
        else{
            dp[0] = 1;
            dp[1] = 1;

            for(int i = 2;i<n;i++){
                dp[i] = dp[i-2] + dp[i-1];
            }

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


    }
}