[백준] 피보나치 수 2 (BufferedReader, 동적 계획법 DP, 2748번, Java)

▶ BufferedReader, 동적 계획법 DP를 활용한 간단한 문제가 있어 정리해보고자 합니다.

 

문제설명

입력 & 출력

나의 풀이

 

이번 문제는 동적 계획법의 첫번째 문제입니다. 피보나치 수 알고리즘으로 풀이하면 시간 초과가 발생합니다.

 

먼저 dp 배열을 long타입 전역변수로 초기화합니다. 

 

main문에서 dp를  입력된 N+1만큼의 크기를 가지도록 초기화를 해줍니다.

 

N+1로 배열을 만드는 이유는 동적 계획법(DP)을 사용하여 피보나치 수열을 계산할 때, 0번째부터 N번째까지의 피보나치 수를 저장할 공간을 확보하기 위해서입니다.

즉, 인덱스를 0부터 N까지 사용하기 위해 배열의 크기를 N+1로 설정하는 것입니다.

 

그리고 속도를 빠르게 하기 위해서 메모이제이션을 할 수 있도록 상향식 dp_fibo 함수를 선언하고, 초기값을 설정해줍니다.

 

2번째 인덱스부터 인자로 받은 n까지의 배열을 만들고 해당 dp[n]값을 리턴합니다.

 

main문으로 돌아와서 함수를 호출하여 마무리 했습니다.

 

동적계획법 DP에 대한 설명은 아래 포스팅에서 확인 가능합니다 :)

 

 

참고 ❗

[JAVA] 입출력, BufferedReader, StringTokenizer

[Algorithm] 동적 계획법(Dynamic Programming, DP) 알아보기