백준 1003번 : 피보나치 함수
1. 문제 설명 (1003)
다음 소스는 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); } } | cs |
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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
2. 분류
3. 풀이
사실 풀다가 틀린 이유가 저 코드를 그대로 복붙해서 썼기 때문인 것 같다. 시간 제한이 0.25초로 꽤 짧은데, 그대로 복붙하니 40번 피보나치 함수 돌리면 폭발할 수 밖에…(미안해지네)
어쨌든 점화식을 구하기 위해 input과 output을 보면,
| input | fibonacci(0) | fibonacci(1) |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 1 |
| 3 | 1 | 2 |
| 4 | 2 | 3 |
| 5 | 3 | 5 |
와 같이 나왔다. 전형적인 피보나치 함수.
그래서 DP를 활용했다. 출력되는 0과 1의 갯수를 담을 배열을 각각 zero[41], one[41] 로 만들었다.
두 배열 모두 점화식은 x[n] = x[n-1] + x[n-2] 이므로, zero[40], one[40]까지 메모이제이션을 진행한 후 input에 따라 출력했다.
4. 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | import java.io.*; public class Q1003 { static int[][] answer; public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int[] zero = new int[41]; int[] one = new int[41]; zero[0] = 1; zero[1] = 0; one[0] = 0; one[1] = 1; for(int i = 2; i <= 40; i++) { zero[i] = zero[i-1] + zero[i-2]; one[i] = one[i-1] + one[i-2]; } int T = Integer.parseInt(br.readLine()); for(int i = 0; i < T; i++) { int temp = Integer.parseInt(br.readLine()); bw.write(zero[temp]+" "+one[temp]+"\n"); } bw.flush(); bw.close(); } } | cs |
5. 결과
148ms로 잘 작동한다.
댓글남기기