https://www.acmicpc.net/problem/2193

이 문제 또한 노가다를 먼저시작함. 한 규칙찾는데 30분 걸린듯?

이렇게 하니까 규칙이 바로 보여서 코드 바로짬..

오늘 오르막수에서 개털려서 조금 쉽게 느껴짐.

주의할점

unsigned long long으로 해야됨. int로는 갯수가 커버가 안됨. 또한 갯수가 음수는 나올 수 없기 때문에

C++ 코드

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

#define MAX 90 + 1

unsigned long long cache[MAX];

unsigned long long DP(int n)
{
	// 기저
	if (n <= 3) return cache[n];

	// 캐시
	unsigned long long& ret = cache[n];
	if (ret != 0) return ret;

	// 구함
	return ret = DP(n - 1) + DP(n - 2);
}

int main()
{
	memset(cache, 0, sizeof(cache));

	cache[0] = 0;
	cache[1] = 1;
	cache[2] = 1;
	cache[3] = 2;

	int n;
	cin >> n;

	unsigned long long ret = DP(n);
	cout << ret;

	return 0;
}