코드업(CodeUp) - C 1856번 - [기초-재귀함수] 계단 뛰어 오르기

문제 : https://codeup.kr/problem.php?id=1856

[기초-재귀함수] 계단 뛰어 오르기

 

문제 설명

*주의사항 : 이 문제는 재귀 설계 문제로서 반복문을 사용한 코드는 채점이 되지 않습니다.
------

한 번에 계단을 1개 또는 2개 또는 3개를 뛰어 오를 수 있을 때,
한 정수 n을 입력받아 바닥(0번째 계단)에서 n번째 계단까지 도착할 수 있는 방법의 가짓수를 출력하시오.
(단, 반복문은 사용할 수 없다.)

예를 들어, 
1번째 계단에 도착하는 방법은 1가지 뿐이고,
2번째 계단에 도착하는 방법은 2가지(1개-1개 뛰기, 2개 뛰기),
3번째 계단에 도착하는 방법은 4가지(1개-1개-1개, 1개-2개, 2개-1개, 3개) 이다.


참고
다중 재귀는?
함수를 정의하는 도중에 자기 자신을 2번 이상 호출하는 방법이다.
하향식 방법은?
큰 문제의 답을 얻기 위해서 이전에 얻어낸 같은 형태의 보다 작은 문제의 해결 결과를 이용하는 방법이다.


n번째 계단에 도착할 수 있는 방법의 가짓수를 계산하는 문제는
다음과 같은 다중 재귀 하향식 방법으로 설계하여 해결할 수 있다.

n번째 계단에 도착할 수 있는 방법의 가짓수를 출력하는 문제의 하향식 재귀 설계 방법(예시)
- 하향식
n번째 계단에 도착할 수 있는 방법의 가짓수는 다음과 같이 문제를 쪼개어 해결할 수 있다.

n번째 계단에 도착할 수 있는 방법의 가짓수는
(n-3)번째 계단까지 와서 3개를 뛰어 n번째 계단에 도착하는 방법의 가짓수 +
(n-2)번째 계단까지 와서 2개를 뛰어 n번째 계단에 도착하는 방법의 가짓수 +
(n-1)번째 계단까지 와서 1개를 뛰어 n번째 계단에 도착하는 방법의 가짓수 이다.
... 
3번째 계단까지 도착할 수 있는 방법의 가짓수는 4 이다.
2번째 계단까지 도착할 수 있는 방법의 가짓수는 2 이다.
1번째 계단까지 도착할 수 있는 방법의 가짓수는 1 이다.


재귀 함수를 정확하게 설계하기 위해서는

1. 가장 먼저! : 자신이 만들고자하는 “재귀 함수의 의미”를 명확하게 생각한 후,

2. 그 다음에 : “큰 문제와 작은 문제 사이의 관계(하향식)”나 “현재 상태에서 다음 상태로의 변화관계(상향식)”와 같은 
관계를 분석해 작성하고,

3. 마지막에 : “가장 작은 문제 상태”나 “가장 큰 문제 상태”를 생각해
재귀 호출의 중단 조건과 그 상태에서의 리턴 값을 작성해 넣으면 된다.

금지 키워드 : while goto for

 

 

입력

int 형 정수(n) 1개가 입력된다.
(1 <= n <= 25)

출력

0 번째 계단에서 시작해서 한 번에 1개/2개/3개의 계단을 뛰어넘을 수 있을 때, n 번째 계단에 도착할 수 있는 방법의 가짓수를 출력한다.

입력 예시

3

출력 예시

4

 

 

코드 : 

# include <stdio.h>

int m;

int print(int n)
{
	if(n == 1)
		return 1;
	else if(n == 2)
		return 1+print(1);
	else if(n == 3)
		return 1 + print(1) + print(2);
	else
		return print(n-3) + print(n-2) + print(n-1);
}


int main()
{
	scanf("%d",&m);
	printf("%lld",print(m));
	
	return 0;
}