계단오르기(Top-Down : 메모이제이션)

Dynamic programming(동적계획법)

문제 ✏️

계단오르기(Top-Down : 메모이제이션)

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

▣ 입력설명
첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다.

▣ 출력설명
첫 번째 줄에 올라가는 방법의 수를 출력합니다.

▣ 입력예제 1
7

▣ 출력예제
21

코드 💻

import sys
#sys.stdin = open("input.txt", "rt")			# read text

def DFS(len):
    if dy[len] > 1:
        return dy[len]
    if len == 1 or len == 2:
        return len
    else:
        dy[len] = DFS(len-1) + DFS(len-2)
        return dy[len]

if __name__ == "__main__":
    n = int(input())
    dy = [n] * (n + 1)
    print(DFS(n))

참고

• 인프런 : 파이썬 알고리즘 문제 풀이