[CodeUp] 3704번 : 계단 오르기 2 (Python)

Python

방법 1 - 메모리 56316 / 시간 103 / 코드 길이 386B

본 문제를 푸는데 중요한 아이디어는 1,2,3 계단 씩 오를 수 있다는 것이다.

가령 우리가 계단 1개를 오른다고 하면 당연히 1계단을 올라 1이다.

이 때의 Lv1 = 1 (Lv는 단계를 의미한다.)

계단이 2개인 경우를 Lv2라고 할 때

1+1, 2

이렇게 2가지가 존재한다. Lv2=2

계단이 3인 경우

1+1+1

1+2

2+1

이렇게 4가지가 존재한다. Lv3 = 3

그런데 계단이 3인 경우를 다시 생각해보면 Lv1에서 2 계단을 오르면 Lv3이 되고 Lv2에서 1계단을 오르면 Lv3이 되고 아이에 처음부터(Lv0) 3단계를 오르는 경우 또한 생각해볼 수 있다.

Lv0	0	+3 계단	0+3=3
Lv1	1	+2 계단	1+2=3
Lv2	1+1	+1 계단	1+1+1=3
Lv2	2	+1 계단	2+1=3

마찬가지로 계단이 n일 때는 어떨까

Lv (n-3)	i 가지	+3 계단
Lv (n-2)	j 가지	+2 계단
Lv (n-1)	k 가지	+1 계단

Lv n의 요구하는 값은 (i+j+k) 임을 확인할 수 있다.

그렇다면 이를 재귀 문제로 다음과 같이 풀 수 있다.

import sys
sys.setrecursionlimit(100000)

def r(n, a):
  if n == 1:
    a[1]=1
    return a[1]
  elif n==2:
    a[2] = 2
    return a[2]
  elif n==3:
    a[3] = 4
    return a[3]

  #print(a[:100])
  if a[n]:
    return a[n]
  else:
    a[n] = (r(n-3, a)+r(n-2, a)+r(n-1, a)) % 1000
    return a[n]
    
n = int(input())
a = [0 for _ in range(n+1)]
print(r(n, a))