[Inflearn] 돌다리 건너기(DP : Bottom-Up)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다.  철수가 개울을 건너는 방법은 몇 가지일까요?

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

마찬가지로 점화식을 구하면 된다.

돌다리를 건너는 방법은 

1번 - 1가지(1칸)

2번 - 2가지(1+1칸, 2칸)

3번 - 3가지(1번에서 2칸 건너서, 2번에서 1칸 건너서)

...

점화식

D(n) = D(n-2) + D(n-1) 

을 구할 수 있다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <cstdio>   int dp[50] = { 0, 1, 2, };   int main(void) {     int n, i;     scanf("%d", &n);       for (i = 3; i <= n+1; i++) {         dp[i] = dp[i - 2] + dp[i - 1];     }       printf("%d\n", dp[n+1]);       return 0; } Colored by Color Scripter

cs

완전히 건너려면 마지막에 돌 다리가 하나 더 있다고 생각해야 한다.

그러므로 n+1까지의 해를 구한다고 생각하면 된다.

#. Result

  - Input --------------------------------------------------------

7

------------------------------------------------------------------

  - Output --------------------------------------------------------

34

------------------------------------------------------------------