#2193 이친수

# 문제

# 입력 및 출력

# 풀이

dp[i]의 이친수는 dp[i-1]자리 이친수에 '0'을 붙이거나, dp[i-2]자리 이친수에 '01'을 붙인 수가 된다

따라서 점화식은 dp[i] = dp[i-1] + dp[i-2]

 

#include <iostream>
using namespace std;
long long dp[91] = { 0,1,1, };

int main() {
	int N;
	cin >> N;
	for (int i = 3; i <= N; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	cout << dp[N];
}

 

dp를 int형 배열로 선언하면 어떤 수부터 int형 범위를 넘어 터지기 때문에

long long배열로 선언해주었음