[C/C++] 코드업(codeup) 3704번 계단 오르기 2

▽문제 바로가기

https://codeup.kr/problem.php?id=3704

계단 오르기 2

---

입력

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

 

출력

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

 

 

문제 풀이

 

이 문제 역시 먼저 규칙을 찾아야 합니다. 풀고 나니 허무한데 0계단을 1가지 경우의 수를 가진다고 가정하니 쉽게 풀렸습니다. 0계단은 1가지 경우의 수를 가지는 것은 말도 안 되는 일이지만, 문제의 계단 입력의 범위는 1부터 100,000까지이니 상관없을 것 같습니다.

 

그리고 손으로 5단계까지는 쉽게 경우의 수를 찾을 수 있습니다.

계단(n)	0	1	2	3	4	5
경우의 수	1	1	2	4	7	13

 

f(n) = f(n-3) + f(n-2) + f(n-1)이라는 식을 얻을 수 있습니다.

 

식을 알았으니 바로 코드를 작성할 수 있습니다.

 

#include <stdio.h>

//0계단 경우의수 부터 차례대로 1, 1, 2
//메모이제이션 배열
int memo[100001]={1, 1, 2};

int recur(int a){
	if(a==1) return 1;
	
	//메모된 값이 있다면 함수 호출하지 말고 바로 리턴
	if(memo[a]!=0) return memo[a];
    
	else return memo[a] = (recur(a-1) + recur(a-2) + recur(a-3))%1000;
}

int main(){
	
	int a;
	scanf("%d", &a);
	printf("%d\n", recur(a));
	
	return 0;
}

 

재밌는 사실은 함수 호출 과정에서 순서를 바꾸면 속도가 달라진다는 것입니다.

 

else return memo[a] = (recur(a-1) + recur(a-2) + recur(a-3))%1000;

else return memo[a] = (recur(a-3) + recur(a-2) + recur(a-1))%1000;

 

누가 더 빠를까요?

정답은 밑이 더 빠릅니다. 함수 호출 순서, 규칙을 통해 알아낸 점화식 그리고 메모이제이션기법을 통해 밑에 코드가 함수를 더 적게 호출합니다.