백준14495 피보나치 비스무리한 수열

작성일 | In

문제 링크

  • http://icpc.me/14495

문제 출처

  • 2017 선린 봄맞이 대회 I번

사용 알고리즘

  • DP

시간복잡도

  • O(n)

풀이

i번째 수는 (i-1번째 수) + (i-3번째 수)입니다.
dp[i]를 i번째 수라고 하면 dp[i] = dp[i-1] + dp[i-3]이 됩니다.

이 점화식을 코드로 그대로 옮기면 AC를 받을 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[120];

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