알고리즘/문제풀이 - 백준

백준 1003 피보나치 함수

문제 : https://www.acmicpc.net/problem/1003 서론 DP문제이며 메모이제이션을 이용하여 풀이했다. 아이디어 n 0 1 2 3 4 5 6 7 8 피보나치 0 1 1 2 3 5 8 13 21 0의 개수 1 0 1 1 2 3 5 8 13 1의 개수 0 1 1 2 3 5 8 13 21 위 표를 보면 규칙성이 있는데, 피보나치 수열과 1의 개수 수열은 같다. n이 0일때를 제외하고, 피보나치 수열의 n은 0의 개수 수열의 n+1과 같다. 따라서 0의 개수는 n번째 피보나치수를, 1의 개수는 n-1번째 피보나치 수를 출력하면 된다. 메모이제이션 함수에서 fib(n) = fib(n-1) + fib(n-2)를 계산할때 이미 fib(n-1)과 fib(n-2)를 이전에 계산한적이 있어서 배열에..

2019. 6. 28. 21:35