[C++] 계단오르기(Top-Down : 메모이제이션)

📄문제

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.
그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

 

⬇️ 입력

첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다.

7

 

⬆️ 출력

첫 번째 줄에 올라가는 방법의 수를 출력합니다.

21

 

📝 풀이

#include <iostream>
using namespace std;

int dp[46];

int DFS(int n)
{
	if (dp[n] != 0)
		return dp[n];

	return dp[n] = DFS(n - 1) + DFS(n - 2);
}

int main()
{
	ios_base::sync_with_stdio(false);

	int N;

	dp[1] = 1;
	dp[2] = 2;

	cin >> N;
	cout << DFS(N);
}

• 계단을 오르는 방법은 1칸, 2칸을 오르는 방법으로 F(n) = F(N-1) + F(N-2)로 구할 수 있습니다.