👀 문제
https://www.acmicpc.net/problem/1003
👊 도전
1. 설계
- DP의 Bottom-Up 방식으로 이용한다.
- Memorization 기법 사용을 위해 배열을 둔 뒤, 작은 문제부터 해결해내가며 값을 저장하고, 중복호출 시 메모리 값을 재활용한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Scanner;
/**
*
* @author HEESOO
*
*/
public class Main {
public static void main(String[] args){
Scanner input=new Scanner(System.in);
int t=input.nextInt();
int[][] array;
int n;
for(int i=0;i<t;i++){
n=input.nextInt();
if(n==0){
System.out.println("1 0");
continue;
}
else if(n==1){
System.out.println("0 1");
continue;
}
else{
array=new int[n+1][2];
array[0][0]=1;
array[1][1]=1;
for(int j=2;j<=n;j++){
array[j][0]=array[j-1][0]+array[j-2][0];
array[j][1]=array[j-1][1]+array[j-2][1];
}
System.out.println(array[n][0]+" "+array[n][1]);
}
}
}
}
3. 결과
🤟 성공 🤟
평소 이클립스 실행 후 맞으면 백준에 채점하는데, 이클립스 패키지 이름을 지우지 않아서 런타임 에러가 발생했다.
4. 설명
- DP의 Bottom-Up방식을 이용한다.
- n이 0, 1이라면 이 이상의 계산은 무의미하므로 출력 후 다음 문제로 넘어간다.
- 배열 array는 Memorization기법을 위해 사용되는 메모리이다. array[n+1][2]로 선언하여, 0부터 n까지의 숫자를 피보나치로 계산할 때 0과 1이 호출되는 횟수를 [i][0], [i][1]에 저장한다.
- n이 0이면 array[0][0]=1을 넣어 n이 0인 경우에는 fib(0)호출이 한 번 일어난다는 것을 알려준다. 이때 fib(1)은 호출되지 않았으므로 array[0][1]=0이다.
- 1도 위와 마찬가지로 하면 array[1][1]=1을 저장하고, n이 2부터 n까지 차례대로 진행하며 array[i][0], array[i][1]에 값을 넣는다.
- 이때 피보나치 공식 fib(n)=fib(n-1)+fib(n-2)에 맞게 array[i][0]=array[i-1][0]+array[i-2][0]으로 구할 수 있다. array[i][1]도 마찬가지이다.
👏 해결 완료!
참고
- [BOJ] 백준 1003 - 피보나치 함수 (자바) https://zoonvivor.tistory.com/157