Algorithm - 돌다리 건너기(동적 계획법)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[돌다리 건너기(동적 계획법)]

 

철수는 학교에 가는데 개울을 만났다. 

개울은 N개의 돌로 다리를 만들어 놓았으며, 철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 돌다리를 건널 수 있다. 철수가 개울을 완전히 건너는 방법의 수를 출력하는 프로그램을 작성하시오.

 

 

 

*입력 설명

첫 번째 줄에 돌의 개수인 자연수 N(3 ≤ N ≤45)이 주어진다.

 

*출력 설명

첫 번째 줄에 개울을 건너는 방법의 수를 출력한다.

 

 

---

 

 

풀이(Python)

답안(1) : Bottom-Up

import sys
sys.stdin = open('AA/input_75.txt', 'rt')

n = int(input())
dy = [0]*(n+2)

dy[1] = 1
dy[2] = 2

for i in range(3, n+2):
    dy[i] = dy[i-1] + dy[i-2]
    
print(dy[n+1])

# 출력 : 34

 

답안(2) : Top-Down(재귀함수 & 메모이제이션)

import sys
sys.stdin = open('AA/input_75.txt', 'rt')

def DFS(len):
    if dy[len] > 0:         # 메모이제이션(컷엣지)
        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 = [0] * (n+2)
    print(DFS(n+1))
    
# 출력 : 34

 

input_75.txt(입력)

7

 

 

중요내용

1. 개울을 완전히 건너는 것은 n번째 돌에 도착하는 것이 아니라 n번째 돌 다음에 나오는 땅에 도착하는 것을 의미한다.
2. 이것이 for문을 통해 3부터 n+1까지 반복문을 실행하고, dy[n+1]과 DFS(n+1)을 print문으로 출력하는 이유이다.
3. 기본적인 문제 접근방식은 네트워크선 자르기 문제와 동일하다.