[JAVA] 피보나치 - DP

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

생각과정

- 피보나치를 재귀 함수로 구현했을 때, 리턴값이 0 또는 1이 되는 횟수를 각각 출력해야 한다.

- 시간 절약을 위해 Bottom-up DP를 선택.

- n 값이 0일 때, 0 개수는 1, 1 개수는 0이다.

- n 값이 1일 때, 0 개수는 0, 1 개수는 1로 출력된다.

- 피보나치 함수는 n이 실행되면 n-1, n-2 함수를 각각 실행시키기 때문에 n 값이 2일 때 0과 1의 개수는 각각 n-1번째 값과 n-2번째 값을 더한 것과 같다.

- 초기값 0, 1은 메모 배열에서 미리 초기화시킨다.

 

구현

package baekjoon;

import java.util.Scanner;

public class b1003 {
	
	public void b1003(int n) {		
		int[]m1 = new int[n+3];
		int[]m2 = new int[n+3];

		m1[0] = 1;
		m1[1] = 0;
		m1[2] = 1;
		
		m2[0] = 0;
		m2[1] = 1;
		m2[2] = 1;
		
		
		for(int i=3;i<=n;i++) {
			m1[i] = m1[i-1] + m1[i-2];
			m2[i] = m2[i-1] + m2[i-2];
		}
		
		System.out.println(m1[n] + " " + m2[n]);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		b1003 b = new b1003();
		
		int num = s.nextInt();
		int []n = new int[num];
		
		for(int g=0;g<num;g++) {
			n[g] = s.nextInt();
		}
		
		for(int g=0;g<num;g++) {
			b.b1003(n[g]);
		}
		
	}

}

 

결과

C++에 비해서 메모리가 많이 쓰였다..

 

 

Dynamic Programming

DP는 이전 상태를 저장하는 배열을 만들어 다음 상태를 구할 때 사용하는 기법이다. 문제에 따라 Top-Down 방식이나 Bottom-Up 방식을 사용하는데, 이 문제에서는 재귀함수의 return 부분부터 시작하기 때문에 Bottom-Up 방식을 사용했다.

Bottom-Up 방식은 for문을 사용해 Top-Down의 재귀보다 시간이 절약된다는 장점이 있다. 위 문제에서는 메모제이션을 할 두 배열 m1, m2를 만들었는데, 각각 0의 출력횟수와 1의 출력횟수를 저장한다. n이 0이거나 1일때는 계산이 간단하기 때문에 미리 이전값으로 정해두면 n의 숫자가 커져도 이전 값들이 메모되어 있어서 값을 편리하게 구할 수 있었다.

DP에서 가장 중요한 부분은 점화식을 찾는 것이다. 이번에는 점화식을 간단히 알아냈지만 어려운 문제를 풀려면 연습이 많이 필요할 것 같다.

 

 

참고

https://data-make.tistory.com/384

[Algorithm] DP(Dynamic Programming), 동적 계획법 (Bottom-Up, Top-Down)