백준 2193번: 이친수

[문제 링크]

2193번: 이친수

---

간단한 DP문제였다. 이친수의 규칙을 살펴보면 N이 1씩 증가할때 이친수 갯수의 수열은 피보나치 수열을 이룬다.

따라서, 점화식은 DP(N) = DP(N-1) + DP(N-2) 이며 이를 구현하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
using namespace std;

long long memo[91];

long long TopDown(int N)
{
	if (N == 1 || N == 2) return 1;

	long long& ret = memo[N];
	if (ret != 0) return ret;

	return ret = TopDown(N - 1) + TopDown(N - 2);
}

long long BottomUp(int N)
{
	memo[1] = memo[2] = 1;

	for (int i = 3; i <= N; i++)
		memo[i] = memo[i - 1] + memo[i - 2];
	
	return memo[N];
}

int main(void)
{
	int N;
	cin >> N;

	// Top-Down
	cout << "TopDown: " << TopDown(N) << endl;
    
	// Bottom-Up
	cout << "BottomUp: "<< BottomUp(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 64 day