[백준 2193] 이친수

문제 링크 => 2193번: 이친수 (acmicpc.net)

2193번: 이친수

---

다이나믹 프로그래밍 문제이다.

 

사실 이문제는 n=6 까지만 해봐도 피보나치의 규칙성이 보이는 단순한 문제이다.

 

이때 n값이 90까지이므로 int형으로 선언할 경우 틀리게 되므로 long long 을 붙여주도록 하자.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

long long d[91];

void dp(int n) {
	d[1] = 1, d[2] = 1;
	for (int i = 3; i <= n; i++) {
		d[i] = d[i - 1] + d[i - 2];
	}
	cout << d[n] << endl;
	return;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	dp(n);
	
	return 0;
}