[인프런] 계단오르기

문제

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.
그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

[입력설명]
첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다.
[출력설명]
첫 번째 줄에 올라가는 방법의 수를 출력합니다.

입력예제 1

7

출력예제 1

21

 

문제풀이

계단을 한칸 또는 두칸만 갈수 있다!!

 

1번 계단으로 갈 수 방법의 수는 1

 - 한칸 오름

2번 계단으로 갈 수 있는 방법의 수는 2

 - 두칸 오름

 

그렇다면 3번 계단은 ?

3번 계단으로 갈수 있는 방법의 수 중 끝이 한칸 오르는

 - 2번에서 오는 경우 ->> 2번 계단으로 갈 수 있는 방법의 수는 2

3번 계단으로 갈수있는 방법의 수 중 끝이 두칸으로 오르는

 - 1번에서 오는 경우 ->> 1번 계단으로 갈 수 방법의 수는 1

#계단을 한번에 하나, 또는 두개만 오르르 수 있는 경우
n = int(input())
dy = [0] * (n + 1)

dy[1] = 1       #1번 계단을 올라갈 수 있는 방법의 수
dy[2] = 2       #2번 계단을 올라갈 수 있는 빙법의 수

#3부터 n까지 구한다
for i in range(3, n+1) :
    #dy[3] = dy[2] + dy[1]
    dy[i] = dy[i-1] + dy[i-2]
    
print(dy[n])

 

추가

계단을 한칸 또는 두칸 또는 세칸 갈수 있다!!

 

1번 계단으로 갈 수 방법의 수는 1

 - 한칸 오름

2번 계단으로 갈 수 있는 방법의 수는 2

 - 두칸 오름

 

그렇다면 3번 계단은 ?

3번 계단으로 갈수 있는방법의 수 중 한칸 오르는 경우

 - 2번에서 오는 경우 ->> 1번 계단으로 갈 수있는 방법의 수 1

3번 계단으로 갈수있는 방법의 수 중 두칸 오르는 경우

 - 1번에서 오는 경우 ->> 2번 계단으로 갈 수있는 방법의 수 2

3번 계단으로 갈수 있는 방법의 수 중 세칸 오르는 경우

 - 0번에서 오는 경우 ->> 0번 계단으로 갈 수있는 방법의 수 1

#계단을 한번에 하나, 또는 두개 또는 세개만 오르르 수 있는 경우
n = int(input())
dy = [0] * (n + 1)

dy[0] = 1       #1번 계단을 올라갈 수 있는 방법의 수
dy[1] = 1       #2번 계단을 올라갈 수 있는 빙법의 수
dy[2] = 2       #0에서 오기(세개 오름), 1에서 오기(2개 오름), 2에서 오기(1개 오름)

#3부터 n까지 구한다
for i in range(4, n+1) :
    #dy[3] = dy[2] + dy[1] + dy[0]
    dy[i] = dy[i-1] + dy[i-2] + dy[i-3]
    
print(dy[n])