[백준 2193번] 이친수 (C++)

문제링크 : https://www.acmicpc.net/problem/2193

 

#include <bits/stdc++.h> 
using namespace std;

int n;
long long dp[91];  //크기가 커서 long long으로 선언

int main()
{
	cin >> n;
	dp[1] = 1, dp[2] = 1;
	for (int i = 3; i <= n; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];  //피보나치 수열과 동일
	}
	cout << dp[n];
}

 

경우의 수를 나열하다보면 피보나치 수열과 같은 규칙을 따른다는 것을 알 수 있다.