[JAVA] BOJ(백준) - 피보나치 함수 - 1003

문제 내용

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

1003번: 피보나치 함수

 

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

 

---

문제 접근 방법

DP에 대한 문제인데 처음엔 그냥 피보나치를 구현해서 0 과 1이 호출되는 갯수를 세고 출력했다. 결과는 당연히 시간초과로 실패 ㅎㅎ..

 

그리고 DP에대한 개념을 공부하고 풀려고 했지만 나는 너무 어렵게 느껴졌고,, 어떻게 풀지 감도 안잡혔다.

그래서 처음엔 구글링을 통해 다른분 블로그를 참고해서 무작정 똑같이 따라쓰면서 이해하려고 했고 그 결과를 말해보고자 한다.

 

내가 이해한 것을 토대로 말해보자면.

먼저 규칙을 찾아서 식을 세워야하는데 이를 점화식? 이라고 말하는듯 하다.

그리고 점화식은

n일때 0호출 횟수 == n-1일때 0호출횟수 + n-2일때 0호출횟수

n일때 1호출 횟수 == n-1일때 1호출횟수 + n-2일때 1호출횟수

라는 규칙으로 식을 세울수 있다.

 

DP 방식대로 계산했던 값을 배열에 저장해놓고 필요할때 다시 계산하지 않고 꺼내쓰기 위해 위에서 말한 규칙을 이용하면 된다.

 

그러기 위해선 먼저

DP 배열을 만들어야 하는데 DP배열을 만드는 방식은 정해져 있는건 아니지만 여기선 2차원 배열을 사용한다.

dp 배열에서 행이 숫자 N일때 열은 0,1을 나타내고 할당되는 값은 호출 횟수가 된다.

즉, 'dp[N][0 or 1] = 호출 횟수' 로 정의한다.

 

그럼 dp 배열을 위의 규칙에 적용해보면

dp[N][0] = dp[N-1][0] + dp[N-2][0];

dp[N][1] = dp[N-1][1] + dp[N-2][1];

이라고 할 수 있다.

 

그리고 N일때 0과 1의 호출 횟수를 구하기위해선 N-1 과 N-2일때를 알아야하고 N-1과 N-2도 마찬가지로 반복되는 과정을 통해 하나씩 알아가야한다.

그 반복을 재귀를 통해서 알아가면 된다.

 

정리하면, 만약 첫 입력값으로 N=40이 들어온다면 재귀를 통해 40까지 0과 1의 호출 횟수를 dp 배열에 저장해 놔서 그 후로 두번째, 세번째 입력값으로 40이하 숫자가 들어오면 dp[N][0] 과 dp[N][1]을 바로 꺼내 쓰면되기 때문에 다시 계산할 필요가 없다.

 

마찬가지로 첫 입력값이 20 이 들어오면 첫 값은 재귀를 통해 0과 1의 호출 횟수를 dp 배열에 저장해 놓고 후에 20이상 숫자가 들어왔을때 20까지는 미리 계산해놓은 dp배열을 활용하고 나머지는 재귀를 통해 계산해 dp 배열에 추가면 되는 것이다.

 

풀이를 보면서 생각해보자.

풀이는 다른분의 블로그 코드를 똑같이 쓴 코드와

백준에서 본 풀이로 나눴고 백준 풀이도 결국 같은 규칙을 이용했기 때문에 이해하기 쉽다.

 

주석은 내가 이해한 방식으로 달아놨다.

---

풀이

블로그 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1003_1 {
	static int T; //테케
	static Integer[][] dp = new Integer[41][2]; //dp배열
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		T = Integer.parseInt(br.readLine());
		
		//초기화 -> N이 0일때와 1일땐 호출횟수를 초기화 해줌.
		//dp특성상 가장 작은 기저값은 파악할수 있어야한다고 함.
		dp[0][0] = 1;
		dp[0][1] = 0;
		dp[1][0] = 0;
		dp[1][1] = 1;
		
		for(int i=0; i<T; i++) {
			int N = Integer.parseInt(br.readLine());
			fibonacci(N);
			sb.append(dp[N][0]+" ").append(dp[N][1]+"\n");
		}
		System.out.println(sb.toString());
	}
	
	//top-down 방식으로 생각됨.
	public static Integer[] fibonacci(int N) {
		//N일때 계산했던 적이 없으면 계산해보겠다는 의미
		if(dp[N][0] == null || dp[N][1] == null) {
			dp[N][0] = fibonacci(N-1)[0] + fibonacci(N-2)[0]; //N일때 0호출 횟수
			dp[N][1] = fibonacci(N-1)[1] + fibonacci(N-2)[1]; //N일때 1호출 횟수
		}
		/*
		 * N에대한 주소값(?)을 반환하는데 실제 쓰임새는 재귀를 통해 반환되는 이전 N의 값에 대한
		 * 0과 1의 호출횟수를 간직한 주소값을 반환하는 것.
		 * 만약 N이 30이면 마지막엔 dp[30]이 반환되겠지만 이건 쓸곳없고 실제로는
		 * dp[0~30]중 if문에걸리지 않는(계산안된,null인) 주소값들을 반환하는 것.
		 */
		return dp[N];
	}
}

---

백준 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1003_2 {
	 public static void main(String args[]) throws IOException {
	        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        int n = Integer.parseInt(br.readLine());//테케
	        int[] zero = new int[41];//dp 배열(0 호출 횟수 간직)
	        int[] one = new int[41];//dp 배열(1 호출 횟수 간직)
	        zero[0] = 1;
	        one[1] = 1;

	        //N이 2~41까지 0과 1의 호출횟수를 미리 저장 시켜놓음.
	        //bottom-up 방식인듯.
	        for (int i = 2; i < 41; i++) {
	            zero[i] = zero[i - 1] + zero[i - 2];
	            one[i] = one[i - 1] + one[i - 2];
	        }
	        
	        StringBuilder sb = new StringBuilder();
	        for(int i=0; i<n; i++) {
	            int num = Integer.parseInt(br.readLine());
	            sb.append(zero[num]).append(" ").append(one[num]).append("\n");
	        }
	        System.out.println(sb);
	    }
}

 

---

마무리

처음으로 dp방식을 이용해 풀었는데 빡세다.... 그리고 DP는 내가 생각하기에 푸는 방식 중 하나or개념 일뿐 규칙이 정해져있는 것도 아니라 코드를 이해하고 내꺼로 만드는데 더 시간이 드는듯한 느낌이다.

 

참고로

n의 0 호출 횟수 == n-1일때 1호출 횟수

n의 1 호출 횟수 == n-1일때 1호출 횟수 + n-1일때 0호출 횟수

의 규칙을 이용한다면 dp배열을 쓰지않고 풀수도 있다.

 

https://st-lab.tistory.com/124

[백준] 1003번 : 피보나치 함수 - JAVA [자바]

이블로그에 정리가 잘돼있고 본인도 여기서 이해한거라 한번쯤 들어가서 보면 좋을 것 같다.