[C++] DP - 네트워크 선 자르기(Bottom-Up)

아주 복잡하고 큰 문제를 직관적으로 알 수 있을 정도로 작은 단위로 바꾸고 그 답을 구한 다음
큰 문제로 점차 늘려가며 정답을 구한다.

int dy[50];//다이나믹 배열

#include <iostream>

using namespace std;
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-2]+dy[i-1];//규칙성을 잘 파악해보자
    }
    
    cout << dy[n];
    
    return 0;
}

• 문제에서 주어진 네트워크 선은 3~45미터이다. 이 선을 1m혹은 2m로 잘랐을 때 경우의 수를 구해야 한다.
• 경우의 수 문제이기 때문에 DFS로도 해결할 수 있을 수 있다.
• 하지만, DP의 Bottom-up방식으로도 해결이 가능하다.
• 일단 문제를 아주 작은 단위로 바꾸어본다.
• 1m를 1m혹은 2m로 자르는 방법은? 당연히 1가지이다. 따라서 dy[1] = 1로 기록한다.
• 2m를 1m혹은 2m로 자르는 방법은? 당연히 2가지이다. 따라서 dy[2] = 2로 기록한다.
• 여기까지는 우리가 직관적으로 알 수 있기 때문에 미리 값을 할당시켜놓는다. 
• 문제에서  출력값을 알려줬는데 7m의 경우에는 답이 21이 나온다. 따라서 점화식을 만들어보면
• dy[N] = dy[N-2] + dy[N-1]임을 알 수 있다.
• 참고로, 다이나믹 테이블은 무조건 정답을 기록해놓는 공간이다. 이 문제에서 원하는 출력은 최대 길이이다.
• 따라서, 각 인덱스는 네트워크 선을 의미하며 그 안의 값을 최대 길이가 들어가야만 한다.

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