백준 10870 - 피보나치 수 5

 

www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

오랜만에 PS를 했다. DP 문제로 하나 풀려했는데, 정답률에 맞게 난이도가 쉬웠다.

 

문제)

0번째, 1번째 피보나치 수를 0, 1로 정의한다. 20 이하의 자연수 n을 입력했을 때, n번째 피보나치 수를 출력하시오.

 

풀이)

간단한 dp문제. 1차원 배열로 DP 테이블을 정의하고, 메모이제이션을 이용한 다음 입력받은 n을 인덱싱해서 출력하면 된다.

 

C 코드)

#include <stdio.h>

int n;
int dp[21];

int main() {
	dp[0] = 0;
	dp[1] = 1;
	for(int i=2;i<21;i++) {
		dp[i] = dp[i-2] + dp[i-1];
	}
	scanf("%d", &n);
	printf("%d", dp[n]);
}