백준 알고리즘 2748 (피보나치 수 2) - C++, Python

[문제] 백준 알고리즘 2748 (피보나치 수 2)

> https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

피보나치 문제, DP문제이다.

N이 주어지고, N번째 피보나치 수를 출력하는 문제이다.

유의할 점은, int 형태로는 자료형의 범위를 넘어가서, long long의 자료형을 취한다.

(N = 90일 때 2880067194370816120)

 

[문제 해결]

1. n 입력, long long dp[91]을 정의한다.

2. 점화식 F_n = F_n-1 + F_n-2 (n>=2)을 만족하는 for문을 작성한다.

3. "%lld" (long long 10진수)를 출력한다.

(python은 자료형을 신경쓰지 않아도 된다.)

 

[C++]

#include <cstdio>
using namespace std;

int n;
long long dp[91];

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

 

[Python]

import sys
input = sys.stdin.readline
n = int(input())
dp = [0 for _ in range(n+1)]
dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n])