[COS PRO 1급 #5-1] 우리는 계단도 특별하게 오르죠

문제설명

계단 n칸을 올라가는 방법의 수를 구하려고 합니다. 계단은 한 번에 1계단, 2계단, 3계단씩 오를 수 있습니다.
예를 들어, 계단 3칸을 오르는 방법은 다음과 같이 4가지가 있습니다.

```
1. 1계단 + 1계단 + 1계단
2. 1계단 + 2계단
3. 2계단 + 1계단
4. 3계단
```

계단 수 n이 매개변수로 주어질 때, 계단을 오르는 경우의 수를 return 하도록 solution 함수를 작성하려 합니다. 빈칸을 채워 전체 코드를 완성해주세요.

매개변수 설명

계단 수 n이 solution 함수의 매개변수로 주어집니다.
* n은 3 이상 30 이하인 정수입니다.

return 값 설명

계단을 오르는 경우의 수를 return 합니다.

예시

| n | return |
|---|--------|
| 3 | 4   |
| 4 | 7   |

예시 설명

예시 #1
문제에 나온 예와 같습니다.

예시 #2
계단 4칸을 오르는 방법은 다음과 같이 7가지가 있습니다.

```
1. 1계단 + 1계단 + 1계단 + 1계단
2. 1계단 + 1계단 + 2계단
3. 1계단 + 2계단 + 1계단
4. 2계단 + 1계단 + 1계단
5. 1계단 + 3계단
6. 3계단 + 1계단
7. 2계단 + 2계단
```

문제 코드

def solution(n):
	answer = 0
	steps = [0 for _ in range(n+1)]
	steps[1] = 1
	steps[2] = 2
	steps[3] = 4
	for i in range(4, n+1):
		steps[i] = @@@
	answer = steps[n]
	return answer

풀이

def solution(n):
	answer = 0
	steps = [0 for _ in range(n+1)]
	steps[1] = 1
	steps[2] = 2
	steps[3] = 4
    
	# i번째 계단을 오르는 방법은 1) i-1번째 계단에서 1계단 2) i-2번째 계단에서 2계단 3) i-3번째 계단에서 3계단 오르는 것
	for i in range(4, n):
		steps[i] = steps[i-1] + steps[i-2] + steps[i-3]
	answer = steps[n]
	return answer