아주 복잡하고 큰 문제를 직관적으로 알 수 있을 정도로 작은 단위로 바꾸고 그 답을 구한 다음 큰 문제로 점차 늘려가며 정답을 구한다.
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]임을 알 수 있다.
참고로, 다이나믹 테이블은 무조건 정답을 기록해놓는 공간이다. 이 문제에서 원하는 출력은 최대 길이이다.
