BOJ(백준 온라인 저지) 1003번 with 자바[JAVA]

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

1003번: 피보나치 함수

---

어려웠다. 당연히 재귀함수를 이용하여 풀면 시간초과가 난다.

DP 라는걸 처음 알게되었다.

동적 프로그래밍인데, 이 전의 작업을 다시 사용할 수 있을 때 생각해낼 수 있다.

 

예를 들어 피보나치 수열의 경우

평범한 Recursion 을 이용한다면 수가 많이 커지는 경우 스택 오버플로우가 날 수 있다. 하지만 DP 를 사용한다면 다르다.

 

피보나치 수열을 점화식으로 나타내면

• n=0) F(x) = 0
• n=1) F(x) = 1
• n>1) F(x) = F(x-1) + F(x-2)

이다. 만약 아주 큰 자연수 x 에 대하여 F(x) 를 구한다면 x 가 1까지 작아지는 동안 계속해서 함수를 호출해야 할 것이다. 하지만 이전의 결과를 따로 저장해놓고 다시 사용할 수 있다면 얘기가 다르다. 아주 큰 자연수 x 에 대하여 F(x) 를 구할 때는 F(x-1) 의 값과 F(x-2) 의 값을 다시 사용하면 되는것이다.

 

코드를 보면서 정리하자

import java.io.*;

public class Main {
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		int[] list = new int[82];
		
		list[0] = 1;
		list[1] = 0;
		list[2] = 0;
		list[3] = 1;
		
		for(int i=2; i<41; i++)
		{
			list[i*2] = list[i*2 - 2] + list[i*2 - 4];
			list[i*2 + 1] = list[i*2 - 1] + list[i*2 -3];
		}
		
		String s = "";
		
		for(int i=0; i<T; i++)
		{
			int N = Integer.parseInt(br.readLine());
			
			s += String.valueOf(list[N*2]) + " " + String.valueOf(list[N*2+1]) + "\n";
		}
		
		System.out.print(s);
	}
}

 

@param list 를 보자, list 는 피보나치 값들의 이전 값들을 저장해놓는 리스트이다. n=0 부터 n=40 까지 0의 개수와 1의 개수를 저장해야 하니 길이를 82 로 해주었다.

 

list 를 정의한 후, n=0 과 n=1 의 값을 초기화해준다.

 

그 후 n=40 까지에 대해 list 를 채워준다. 이 때 피보나치의 특징인 그 전 값과 (x-1) 그 전 전 값(x-2) 의 값의 합이 해당 값(x) 임을 이용하여 list 를 채워준다.

이는 재귀를 사용하지 않고 for 문 한 번 만을 사용하기 때문에 x 의 피보나치 값을 찾기 위해 재귀를 도는 것 보다 훨씬 빠르다.

 

그 후는 쉽다. n 값을 받고 n 값에 해당하는 0 의 개수와 1 의 개수가 저장되어 있는 list 의 값을 출력해주면 된다.

 

---

• 느낀 점

이 문제를 봤을 때, 이 전의 값을 다시 사용하면 된다는 생각을 막연하게 했는데, DP 라는 프로그래밍 방법이 있다는 것을 알아내면서 좀 더 나의 생각을 구체화 할 수 있게되었다.

 

만약 N 의 최대값이 40 이 아니라 매우 컸다면 공간 복잡도가 매우 커졌을 것 같다.