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

<문제>

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 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

 

<풀이>

이 문제는 네트워크 선 자르기 문제와 사실상 동일한 문제다. 그치만 이문제를 올리는 이유는 Top-Down 방식이기에 올린다.  Top-Down 방식은 큰 문제를 구하기 위해 작은 문제를 호출하면서 구하는 방식이다.

이문제 같은경우 재귀함수 방식으로 문제를 풀었으나, 단순 재귀가 아닌 메모이제이션 방식으로 문제를 풀었다. 메모이제이션이란 쉽게 말해서 메모에 적으면서 방문할 필요없는 노드들은 방문하지 않는 방식이다. (한번 D(5)의 값을 구했으면 그 밑으로 D(4) D(3)으로 내려가지 않는 방식) 이렇게 가지치기(?)를 통해 시간을 단축시킬 수 있다.

<코드>

def DFS(l):
    if M[l] > 0:
        return M[l]
        
    if l == 1 or l == 2:
        return l
    else:
        M[l] = DFS(l-1) + DFS(l-2)
        return M[l]


n = int(input())
M = [0] * (n+1)
print(DFS(n))

 Bottom-UP , Top-Down 방식 둘다 잘 공부를 해서 문제에 효율적으로 적용할 수 있게끔 해야겠다.