[백준/java] 1003번: 피보나치 함수 - DP(Dynamic Programming)

 

문제

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

1 2 3 4 5 6 7 8 9 10 11

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이 출력되는 횟수를 공백으로 구분해서 출력한다.

 

 

※ 문제 접근 방법 (3번 케이스가 정답 소스입니다.)

(1) 각 N의 0과 1의 갯수 -> 오답

(2) 각 N에서 0과 1이 추가되는 갯수 --> 기하급수적 증가로 인한 메모리 초과

(3) 각 N의 피보나치 값 -> 정답

 

(1) 처음에는 fibonachi(3) 이상은 모든 0과 1의 나오는 갯수가 1, 2로 나오는 줄 알고 풀었으나...

 

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int[] fibo = new int[100];
		int T = Integer.parseInt(br.readLine());
		List<Integer> list = new ArrayList<Integer>();
		while(T-- > 0) list.add(Integer.parseInt(br.readLine()));
		
		for (int i = 0; i < list.size(); i++) {
			int n = list.get(i);
			int[] arr = new int[2];
			
			if(n <= 1) {
				arr[n]++;
				fibo[n] = n;
			}
			
			for (int j = 2; j <= n; j++) {
				int k1 = j-1, k2 = j - 2;
				if(k1 == 0 || k1 == 1) arr[k1]++;
				if(k2 == 0 || k2 == 1) arr[k2]++;
				fibo[j] = fibo[k1] + fibo[k2];
			}
			
			bw.write(arr[0] + " " + arr[1] + "\n");
		}
		
		bw.flush();
	}
}

 

 

결과는..

 

(2) 이번에는 각 피보나치 값이 0과 1을 얼마나 포함하나를 체크하는게 포인트이구나! 싶어서 생각해낸 방법이 바로

밑에 있는 엑셀 캡쳐 이미지이다.

 

1003번: 피보나치 함수 정답 도출 과정

이런 방법이 맞겠다 싶어서

각 N 마다 문자열에 0과 1을 추가하여 최종적인 N의 0과 1의 갯수를 세는 것이 구나 싶었다.

 

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		List<Integer> list = new ArrayList<Integer>();
		
		while(T-- > 0) list.add(Integer.parseInt(br.readLine()));
		
		for (int i = 0; i < list.size(); i++) {
			int n = list.get(i);
			int[] arr = new int[2];
			List<String> strList = new ArrayList<String>();
			
			if(n <= 1) {
				if(n == 1) {
					strList.add("");
				}
				strList.add(String.valueOf(n));
			}
			
			for (int j = 2; j <= n; j++) {
				if(j == 2) {
					strList.add("0"); strList.add("1");
				}
				
				int k1 = j-1, k2 = j - 2;
				String temp1 = strList.get(k1);
				String temp2 = strList.get(k2);
				temp1 = temp1.concat(temp2);
				strList.add(temp1);
			}
			
			for (int j = 0; j < strList.get(n).length(); j++) {
				String str = strList.get(n).substring(j, j+1);
				arr[Integer.parseInt(str)]++;
			}
			
			bw.write(arr[0] + " " + arr[1] + "\n");
		}
		
		bw.flush();
	}
}

 

실행 결과는 잘 나오는 것 같다.

제출 결과..

 

이번엔 메모리 초과다.

 

그도 그럴 것이 메모리 제한이 128MB..

 

아니 메모리 쓰면 뭐 얼마나 쓴다고..

 

하긴 N이 증가할 수록 0과 1이 기하급수적으로 증가하긴 하니까 그런가보다 싶다.

 

(3) 그냥 0과 1의 갯수가 어짜피 각 피보나치 값이니 그냥 각 피보나치 값을 출력하는게 낫겠다 싶었다.

 

package dynamicProgramming;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;

public class FibonacciFunc {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		List<Integer> numList = new ArrayList<Integer>();
		
		numList.add(0); numList.add(1);
		for (int i = 2; i <= 40; i++) numList.add(numList.get(i-1) + numList.get(i-2));
		
		while(T-- > 0) {
			int n = Integer.parseInt(br.readLine());
			
			if(n == 0) {
				bw.write("1 0\n");
			} else if(n == 1) {
				bw.write("0 1\n");
			} else {
				bw.write(numList.get(n-1) + " " + numList.get(n) + "\n");
			}
		}
		
		bw.flush();
	}
}

 

실행 결과..

문자열에 0과 1을 추가하는 방식이랑 똑같이 나왔다.

 

제출을 해봤더니..

 

어휴... 드디어 맞았네..