Algorithm/dynamic programming
[백준] 알고리즘 14495번 - 피보나치 비스무리한 수열 문제
낭강
2021. 3. 28. 20:17
문제
14495번: 피보나치 비스무리한 수열
피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보
www.acmicpc.net
소스코드
#include <bits/stdc++.h>
using namespace std;
long long dp[117];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
dp[1] = 1, dp[2] = 1, dp[3] = 1;
for (int i = 4; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 3];
}
cout << dp[n];
}풀이
점화식이 문제에 있으니 그대로 대입하여 해결한다.