문제 링크 : https://www.acmicpc.net/problem/1003
해결 방법 :
피보나치 함수를 재귀함수, Top-down 방식으로 푼다고 했을 때 fibonacci(0), fibonacci(1) 의 호출 개수를 각각 출력하는 문제다.
처음에는 단순히
if(n == 0) 일때 0의 카운트 증가,
if(n == 1) 일때 1의 카운트 증가로 바로 풀수가 있었는데 채점해보니 시간초과가 떴다.. ㅋ
아 그러면 익히알고있는 다이나믹프로그래밍으로 메모를 쓰고 읽어서 시간을 줄여야 되는 구나라고 생각했다.
테스트 케이스를 가지고 여러번 하다보니 다음과 같은 규칙을 발견했다.
N의 0호출 개수는 N-1의 1호출 개수라는 것
example) 5의 0의 호출개수 = 4의 1의 호출개수, 다른것도 직접해보면 알것이다.
따라서 N과 N-1의 피보나치함수를 호출하고 N==1일때 1의 카운팅을 리턴하여서 각각 총 1의 호출개수를 각각 구할 수 있었다.
이때, 재귀함수에서 여러 N의 1의호출개수를 메모로 저장해둬서(d[N]) 시간을 줄였다.
소스코드)
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 27 28 29 30 31 32 33 34 35 36 37 38 | #include<stdio.h> int d[41]; int fibonacci(int n) { if(n == 0) { return 0; } else if(n==1) { return 1; } else if(n < 0) return 1; else { if(d[n]> 0) return d[n]; d[n] = fibonacci(n-1) + fibonacci(n-2); return d[n]; } } int main() { int n; int T; int one; int zero; scanf("%d",&T); for(int i =0; i<T; i++) { scanf("%d",&n); one = fibonacci(n); zero = fibonacci(n-1); printf("%d %d\n",zero,one); } } | cs |
반응형
'PS > 백준' 카테고리의 다른 글
| 1149번 RGB거리 (0) | 2018.12.05 |
|---|---|
| 7490번 0 만들기 (0) | 2018.12.05 |
| 1065번 한수 (0) | 2018.11.16 |
| 1110번 더하기 사이클 (0) | 2018.11.14 |
| 2448번 별 찍기 - 11 (0) | 2018.11.12 |