- 문제 (1003번)
숫자 N이 주어졌을 때, fibonacci(N) 을 호출했을 때, 0과 1일 각각 몇 번 추력되는지 구하는 프로그램을 작성하시오.
"(즉, fibonacci(N)을 호출했을 때, fibonacci(0)과 fibonacci(1)이 호출되는 횟수 구하기.)"
- 입력 및 출력
[입력]
- 첫번째 줄에는 테스트 케이스의 개수 T가 주어짐.
- 각 테스트케이스는 한줄로 이루어져 있고, N이 주어짐.
( 0 ≤ N ≤ 40, 자연수 )
[출력]
- 각 체스트케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해 출력.
( fibonacci(0)과 fivonacci(1)이 호출되는 횟수 출력 )
- 문제 풀이 ( DP 활용 )
- 이 1003번 문제는 시간이 0.25초로 매우 짧은시간으로 한정되어있기 때문에 DP를 활용해 해결하고자 한다.
1) memoization기법을 활용해 배열에 fibonacci 값 저장
입력받는 N의 값이 0 ~ 40까지의 자연수로 한정되어있기 때문에 어떠한 배열에 0부터 40까지의 fibonacci의 값을 저장해놓는다. ( 이 값이 0과 1을 호출하는 횟수 )
2) 테스트 케이스 값 입력
3) 각각의 N을 입력받아 0과 1을 호출한 횟수 출력
-
fibonacci의 결과값과 0, 1을 호출한 횟수를 정리하다보면 다음과 같은 규칙을 찾을 수 있다.
-
즉 0호출횟수는 fibo(N-1), 1호출횟수는 fibo(N) 이 된다.
(fibonacci는 재귀로 자신을 계속 부르다가 최종적으로 0 또는 1의 값을 더해 자신의 결과값을 결정한다.)
따라서 출력은
" fibonacci(N-1) + " " + fibonacci(N) "
으로 하면 된다.
- 최종 코드
