[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

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 1m, 2m의 길이를 갖는 선으로 네트워크 선을 자르기

  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

입력이 7로 주어진다면

line 

1	2	3	4	5	7	8

먼저 1m로 만들 수 있는 방법은

( 1 ) 하나이다.

line 

1	2	3	4	5	7	8
1

다음으로 2m로 만들 수 있는 방법은

( 1 )

( 2 )  두 가지일 것이다.

line 

1	2	3	4	5	7	8
1	2	3

3m로 만들 수 있는 방법은

2m + 1m 일 경우와 1m + 2m일 경우로 나뉘는데

2m + 1m 로 만들어질 경우, 2 가지 방법이 있고(line[2])

1m + 2m 로 만들어질 경우, 1가지 방법이 있다.(line[1])

둘을 합하면 line[2] + line[1] = 3

line 

1	2	3	4	5	7	8
1	2	3

마찬가지로 진행하면

4m로 만들 수 있는 방법은

마지막 남은 길이가 1m 또는 2m 이어야 아므로

3 + 1

2 + 2 로 만들어질 수 있다. 

이는 마찬가지로 line[2] + line[3] 의 개수와 같다.

line 

1	2	3	4	5	7	8
1	2	3	5

이렇게 f(n) = f(n-2) + f(n-1) 이라는 점화식을 만들 수 있다.

이렇게 DP(dynamic programming)는

직관적으로 구할 수 있는 작은 해를 구한 후, 직관적으로 구한 해를 이용하여 더 큰 문제를 해결해낼 수 있다.

작은 문제의 해를 이용하여 큰 문제의 해를 구해내는 방식을 Bottom-Up 이라고 부른다.

작은 문제의 해를 이용하여 해결하다보면 점화식을 발견할 수 있고 이 점화식으로 큰 문제의 해를 쉽게 구할 수 있다.

#. Code

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

#include <cstdio>   int line[50] = { 0, 1, 2, };   int main(void) {     int N, i;     //freopen("input.txt", "rt", stdin);     scanf("%d", &N);     for (i = 3; i <= N; i++)         line[i] = line[i - 2] + line[i - 1];       printf("%d\n", line[N]);       return 0; } Colored by Color Scripter

cs

#. Other code

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

#include<bits/stdc++.h> using namespace std;   int dy[50]; int main(){     ios_base::sync_with_stdio(false);     int n;     cin>>n;     dy[1]=1;     dy[2]=2;     for(int i=3; i<=n; i++){         dy[i]=dy[i-1]+dy[i-2];     }     cout<<dy[n];     return 0; } Colored by Color Scripter

cs

#. Result

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

7

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

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

21

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