CodeUp / Recursion(재귀) / 3704번 / 계단 오르기2 / C++

문제 설명   

n개의 계단이 있다.

어떤 사람이 계단을 오르려 하는데 이 사람은 계단을 한번에 1계단 2계단 또는 3계단씩 오를 수 있다.

이 사람이 계단을 오를수 있는 경우의 수를 1000으로 나눈 나머지를 구하여라

 

입력

계단의 수 n이 입력된다. ( 1 <= n <= 100,000 )

 

출력

계단을 오를 수 있는 가지수에 1000으로 나눈 나머지를 출력한다.

 

입력 예시  

5

 

출력 예시

13

 

도움말

5=1+1+1+1+1

5=1+1+1+2

5=1+1+2+1

5=1+2+1+1

5=2+1+1+1

5=1+1+3

5=1+3+1

5=3+1+1

5=1+2+2

5=2+1+2

5=2+2+1

5=2+3

5=3+2

이렇게 총 13가지 경우가 존재한다.

 

#include <iostream>
using namespace std;

int arr[100001] = { 1,1,2 }; // 0번째를 1로 둘시, k가 3일때부터 재귀 성립.

int recursion(int k) {
	if (arr[k]) return arr[k];

	else {
		arr[k] = (recursion(k - 3) + recursion(k - 2) + recursion(k - 1)) % 1000;
	}

	return arr[k];
}

int main() {
	int k;
	cin >> k;

	cout << recursion(k) << endl;
}

---

이번 문제도 재귀를 활용할 수 있는 공식을 알아내는 것이 중요했다.

이런 문제가 있을시, 눈으로 짐작이 안되면 직접 손으로 써보면서 하는 것을 추천한다.

5일때 케이스는 문제에 있으니, 6일때 케이스까지 해서 공식을 알아내었다.

항상 느끼지만, 재귀안에 여러 재귀가 들어갈수록 메모이제이션을 해야 시간초과가 안나는 것 같다.

메모이제이션은 어려운 개념이 아니니 꼭 알고가면 유용하게 쓰일 것 같다.