문제 / 돌다리 건너기(Bottom-Up) - 동적계획법 / Python 파이썬

 

문제 제목: 돌다리 건너기(Bottom-Up)

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

개울은 N개의 돌로 다리를 만들어 놓았습니다.

철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다.

철수가 개울을 건너는 방법은 몇 가지일까요?

 

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

▣ 출력설명 첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다.

▣ 입력예제 1

7

▣ 출력예제 1

34

 

---

돌다리를 건널때 한칸 씩 건너뛴다

** 입력값이 7이라고해서 7을 도착지점으로 출력하면 안된다.

문제에서 함정은 마지막에 도착했을 때까지 구해야하는 것이므로 

출력해야하는 값은 8(도착지점)에 대한 출력이다.

나의 풀이

def solution(n):
    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]
    return dy[n+1]

if __name__ == '__main__':
    n = int(7)
    print(solution(n))

출력결과

 

---

※ 알아야 할 것

- 다이나믹 프로그래밍을 할 때 출력해야하는 결과에 대해서도 고려해야함