백준 2193번 c++ 풀이

전략:

1. 3이상의 N에 대하여 N자리 이친수는 N-1자리 이친수 뒤에 0을 붙이는 것과, N-2자리 이친수 뒤에 01을 붙이는 경우이기 때문에 점화식은 pr(num) = pr(num-1) + pr(num-2)가 된다

코드:

#include <bits/stdc++.h>
long long int arr[100]= {0, 1, 1, 2};
long long int pr(int num){
	if(arr[num]){
		return arr[num];
	}
	arr[num] = pr(num-1) + pr(num-2);
	return arr[num];
}
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin>>N;
	cout<<pr(N)<<"\n";
}