n개의 계단이 있습니다. 한 사람은 1~n계단으로 갑니다. 한 걸음에 얼마나 많은 계단을 넘을 수 있는지도 나와 있습니다. 이 정보를 가지고 n번째 계단으로 갈 수 있는 가능한 방법을 찾아야 합니다. 각 단계에서 최대 두 개의 계단을 건널 수 있다고 가정해 보겠습니다. 따라서 이 문제를 해결하기 위해 재귀 관계를 찾을 수 있습니다. (n-1)번째 계단이나 (n-2)번째 계단에서 n번째 계단으로 이동할 수 있습니다. 그래서 way(n) =way(n-1) + way(n-2).
계단의 수를 10이라고 하고 한 단계에서 점프할 수 있는 최대 계단의 수를 2라고 하면 출력은 가능한 89가지가 됩니다.
이 문제를 해결하려면 다음 단계를 따르십시오 -
- 계단 번호와 동일한 크기의 배열 개수 정의
- count[0] :=1
- for i :=2에서 계단 -1까지, do
- 카운트[i] :=0
- j =1 ~ i 및 j <=max; 할
- count[i] :=count[i] + count[i - j]
- 반환 횟수[계단 - 1]
더 나은 이해를 위해 구현을 살펴보겠습니다.
예시(C++)
#include<iostream>
using namespace std;
int stairClimbWays(int stair, int max){
int count[stair]; //fill the result stair using bottom up manner
count[0] = 1; //when there are 0 or 1 stair, 1 way to climb
count[1] = 1;
for (int i=2; i<stair; i++){ //for stair 2 to higher
count[i] = 0;
for(int j=1; j<=max && j<=i; j++)
count[i] += count[i-j];
}
return count[stair-1];
}
int countWays(int stair, int max){ //person can climb 1,2,...max stairs at a time
return stairClimbWays(stair+1, max);
}
int main (){
int stair, max;
cout << "Enter number of stairs: "; cin >> stair;
cout << "Enter max stair a person can climb: "; cin >> max;
cout << "Number of ways to reach: " << countWays(stair, max);
} 입력
Stairs = 10 Max stairs a person can climb: 2
출력
Enter number of stairs: 10 Enter max stair a person can climb: 2 Number of ways to reach: 89