[백준/1003/Java] 피보나치 함수 - 2가지 풀이법
문제:
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
문제분석
다음 소스는 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번 출력됩니다.
fibonacci(N)을 호출하였을 때, 0과 1이 각각 몇 번 출력되는지 구하는 문제입니다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어집니다.
각 테스트케이스는 한 줄로 이루어져 있고, N이 주어집니다. N은 40보다 작거나 같은 자연수 또는 0입니다.
출력
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력합니다.
풀이
이 문제는 C++ 소스를 보시면 0이 출력되는 경우는 if (n == 0)이므로 파라미터가 0으로 호출되는 경우입니다.
1이 출력되는 경우는 if (n == 1)이므로 파라미터가 1로 호출되는 경우입니다.
fibonacci(1)을 붉은 색, fibonacci(0)을 파란색으로 표시하면 이렇게 됩니다.
- fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출합니다.
- fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출합니다.
0, 1이 출력되는 경우를 보기 위하여 피보나치 함수를 모두 호출하면서 계산하기엔 시간이 오래 걸립니다.
따라서, 문제 푸는 것에 집중하여 0, 1이 표시되는 것을 정리하면 이렇게 됩니다.
| N | fibonacci(0) | fibonacci(1) |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 1 |
| 3 | 1 | 2 |
| 4 | 2 | 3 |
| 5 | 3 | 5 |
| 6 | 5 | 8 |
| 7 | 8 | 13 |
| 8 | 13 | 21 |
풀이가 2가지가 나오는데 두 방법을 모두 보도록 하겠습니다.
첫번째 풀이
fibonacci(1)이 호출되는 숫자는 잘 생각해보면 1이 나와서 그 값들을 모두 더해야 피보나치 함수의 결과값이 됩니다.
따라서, 피보나치 재귀함수를 그대로 푸는 수와 동일하므로 이걸 DP로 표시한 것이 D[N] = D[N-1] + D[N-2]입니다.
(문제에 소개된 C++ 소스에서도 표시된 점화식입니다.)
-> return fibonacci(n‐1) + fibonacci(n‐2);
fibonacci(0)을 자세히 보시면 D[0] = 1이면서 D[N] = D[N-1] + D[N-2]의 형태를 지닌 수열이라는 것을 알 수 있습니다.
따라서, fibonacci(1)을 D1이라고 정의하면
D1[0] = 0
D1[1] = 1
D1[N] = D1[N-1] + D1[N-2] 입니다.
그리고 fibonacci(0)을 D0이라고 정의하면
D0[0] = 1
D0[1] = 1
D0[N] = D0[N-1] + D0[N-2] 으로 풀 수 있습니다.
두번째 풀이
위의 표를 다시 자세히 보면 fibonacci(0)과 fibonacci(1)에서 중복되는 패턴이 있다는 것을 알 수 있습니다.
| N | fibonacci(0) | fibonacci(1) |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 1 |
| 3 | 1 | 2 |
| 4 | 2 | 3 |
| 5 | 3 | 5 |
| 6 | 5 | 8 |
| 7 | 8 | 13 |
| 8 | 13 | 21 |
노란색 배경으로 표시해보면
D0[1] = D1[0]
D0[2] = D1[1]
와 같이 1칸씩 어긋나게 차이나는 것을 알 수 있습니다.
예를 들어 N이 5인 경우
fibonacci(0)은 D0[5] = 3입니다.
fibonacci(1)은 D1[5] = 5이지만 D0와 비교하면 D0[6] 값과 동일합니다.
즉, D1[N] = D0[N+1]과 같습니다.
그러면 fibonacci(1)을 구하지 않고 fibonacci(0)을 구한 다음
D0[N]과 D0[N+1]을 출력해도 됩니다.
소스
위에서 구한 점화식을 이용하여 다이나믹 프로그래밍으로 구현하였습니다.
첫번째 소스
fibonacci(0)은 D0 배열로 선언하고
fibonacci(1)은 D1 배열로 선언하였습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main
{
static int N;
static long D0[] = new long[41];
static long D1[] = new long[41];
public static void main(String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
StringTokenizer st = new StringTokenizer(input);
int T = Integer.valueOf(st.nextToken());
for (int test_case = 0; test_case < T; test_case++)
{
input = br.readLine();
st = new StringTokenizer(input);
N = Integer.valueOf(st.nextToken());
D0[0] = 1;
D1[1] = 1;
for (int i = 2; i <= N; i++)
{
D0[i] = D0[i-1] + D0[i-2];
D1[i] = D1[i-1] + D1[i-2];
}
System.out.println(D0[N] + " " + D1[N]);
// System.out.println(Arrays.toString(D0));
// System.out.println(Arrays.toString(D1));
}
}
}
두번째 소스
fibanacci(0)을 D배열에 저장하고 출력할 때 D[N] D[N+1]로 하였습니다.
for문에서 N+1까지 구해야 한다는 점을 유의하시면 됩니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main
{
static int N;
static long D[] = new long[42];
public static void main(String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
StringTokenizer st = new StringTokenizer(input);
int T = Integer.valueOf(st.nextToken());
for (int test_case = 0; test_case < T; test_case++)
{
input = br.readLine();
st = new StringTokenizer(input);
N = Integer.valueOf(st.nextToken());
D[0] = 1;
for (int i = 2; i <= N+1; i++)
{
D[i] = D[i-1] + D[i-2];
}
System.out.println(D[N] + " " + D[N+1]);
// System.out.println(Arrays.toString(D));
}
}
}