[백준] 브1 > 피보나치 수 2 2748번 - JAVA

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

 

제목과 동일

---

Think🤔

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

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 answer = 0;
		
		for(int i=3; i<n; i++){
			answer = fibo(n-1) + fibo(n-2);
		}
		
		System.out.println(answer);
    }
	
	public static Integer fibo(int n){
		if(n == 0){
			return 0;
		}else if(n == 1){
			return 1;
		}else if(n == 2){
			return 1;
		}else{
			return fibo(n-1) + fibo(n-2);
		}
	}
}

 

시간이 초과날 수 밖에 없다..
메모이제이션 동적 계획법 DP를 사용해야함!
이미 계산값을 저장해두는 방법이 메모이제이션입니다.

---

Solution✍

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
		if(n==0){
			System.out.println(0);
			return;
		} else if(n==1){
			System.out.println(1);
			return;
		} else if(n==2){
			System.out.println(1);
			return;
		}  
		
		long [] fibo = new long[n+1];
		fibo[0] = 0;
		fibo[1] = 1;
		fibo[2] = 1;
		
		for(int i=3; i<=n; i++){
			fibo[i] = fibo[i-1] + fibo[i-2];
		}
		System.out.println(fibo[n]);
    }
}

---

Review🤩

 

int로 int[] fibo하면 90같은 큰 숫자의 경우 오버플로우 발생해서 처리하지 못함
long으로 처리해야함..ㄴ

---