Codeup 코드업 2641 숏다리의 계단 오르기 small

문제 설명    내 문제집에 추가 내소스1

NN개의 계단이 있다.

주현이는 계단을 한 번에 1칸 또는 2칸 또는 3칸을 오를 수 있다.

하지만 한번에 3칸을 오른고 나면 힘이 들어 앞으로 두 번은 1칸 또는 2칸만 오를 수 있다.

즉, 한 번에 1칸 혹은 2칸은 조건없이 오를 수 있다. 하지만 3칸을 오르고 나면 적어도 다음 2번의 이동에서는 3 칸을 오르지 못한다. 

계단의 수 NN이 입력되면 주현이가 이 방법으로 계단을 올라갈 수 있는 서로 다른 방법의 수를 계산하는 프로그램을 작성하시오.

입력

첫 번째 줄에 NN이 입력된다.(1<=N<=151<=N<=15)

출력

계단을 오를 수 있는 경우의 수를 출력한다.

입력 예시   예시 복사

4

출력 예시

7

#include <iostream>
using namespace std;

int cnt;
int preprev;

void	upstair(int lev, int prev, int preprev, int n)
{
	if (lev > n)
		return ;
	if (lev == n)
	{
		cnt++;
		return ;
	}
	if (prev != 3 && preprev != 3)
		upstair(lev + 3, 3, prev, n);
	upstair(lev + 1, 1, prev, n);
	upstair(lev + 2, 2, prev, n);
}

int main(void)
{
	int n;
	cin >> n;
	cnt = 0;
	upstair(0, 0, 0, n);
	cout << cnt;
}

	// if (prev == 3 || preprev == 3)
	// {
	// 	upstair(lev + 1, 1, prev, n);
	// 	upstair(lev + 2, 2, prev, n);
	// }
	// else
	// {
	// 	upstair(lev + 3, 3, prev, n);
	// 	upstair(lev + 1, 1, prev, n);
	// 	upstair(lev + 2, 2, prev, n);
	// }

/*
input : 7
output : 42
answer : 41


*/

 

처음에는 prev 만 받아서 했었다. 

upstair(lev + 3, 3, n);

이렇게 

하지만 문제는 3계단을 오른 후에는 2!!!번 동안은 1,2번씩만 이동할 수 있다고.. 

그럼로 직전 뿐만 아니라 과과거도 확인해야 한다. 

따라서 변수 preprev를 만들어서 2번 전의 계단도 확인하도록 했다. 

 

그렇게 되면 upstair(lev + 3, 3, prev, n); 안에 들어간 후에는 prev 가 preprev로 받아진다.