[C++] 돌다리 건너기(Bottom-Up)

📄문제

철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철
수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다.
철수가 개울을 건너는 방법은 몇 가지일까요?

 

⬇️ 입력

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

7

 

⬆️ 출력

첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다.

34

 

📝 풀이

#include <iostream>
using namespace std;

int dp[46];

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

	int N;
	cin >> N;

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

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

	cout << dp[N + 1];
}

• 개울을 건너는  방법은 1칸, 2칸을 지나는 방법으로 F(n) = F(N-1) + F(N-2)로 구할 수 있습니다.
• 여기서 돌을 건너는 개수에서 +1을 해야 돌다리를 완전히 건너는 것 입니다.