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

 

문제설명

입력 & 출력

 

나의 풀이

 

이번 문제는 피보나치 N에서 0과 1의 개수를 출력하는 문제입니다.

 

피보나치수열은 워낙 유명하기 때문에 어렵지 않게 풀 수 있지만 이 문제는 기존의 피보나치 함수를 재귀호출로 푼다면 런타임 에러가 발생합니다.

 

따라서 동적 계획법(DP)를 사용해야 합니다.

 

먼저 피보나치 함수를 점화식으로 표현한다면 다음과 같습니다.

• F(n) = F(n-1) + F(n-2)

위 점화식을 기준으로 이미 계산된 값들을 배열에 저장하여 중복된 계산을 방지해야 합니다.

 

먼저 dp배열을 초기화해줍니다. 첫 번째 배열은 피보나치 수의 인덱스이며, 두 번째 배열은 크기가 2를 가지는 데 0번째는 0의 개수, 1번째는 1의 개수가 들어가게 됩니다.

 

이제 fibo(0)과 fibo(1)은 이미 값이 정해져 있기 때문에 각 값을 초기값으로 설정합니다.

 

초기값을 가지는 0번째와 1번째 수는 조건 없이 설정해도 되지만, 문제의 특성상 T가 1이고 N이 0일 때 예외 상황이 발생할 수 있습니다.

 

이 경우에는 dp 배열의 인덱스를 초과하게 되어 배열 인덱스 오류가 발생할 수 있습니다.

 

따라서 N이 1보다 클 때만 초기값을 설정해 주는 분기 처리가 필요합니다. 그리고 fibo(2)의 값부터는 점화식을 통해 값을 계산하면 됩니다.

 

 

refactoring✅

 

"나의 풀이"와 동일한 로직이지만, 빠른 입력과 출력을 위해서 Buffer를 사용했습니다.

 

그리고 피보나치 수 배열을 전역변수로 선언하고, 초기값을 저장해 줍니다. 그리고 문제의 N의 제한은 0~40이기 때문에 41의 크기를 가지는 배열로 초기화를 해줍니다.

 

그리고 입력을 받아 미리 만들어놓은 배열의 요소를 접근하여 StringBuilder에 추가를 해줍니다.

 

 

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기

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