문제
https://www.acmicpc.net/problem/14495
문제해설
피보나치와 비슷한 수열이 나온다.
n번째의 수를 구하면 된다.
문제풀이
이미 문제에서 f(n) = f(n-1) + f(n-3)이라는 점화식이 주어졌다.
점화식에 맞게 dp를 짜면되고 long long을 써야한다는 것만 주의하자.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll dp[120];
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
dp[1] = dp[2] = dp[3] = 1;
for (int i = 4; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 3];
cout << dp[n];
return 0;
}