91. 네트워크 선 자르기(동적계획법_Bottom-Up 기법) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

#include <iostream>

using namespace std;

int dy[50];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	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] << "\n";
	
	return 0;
}

1. 동적계획법의 가장 기본은 점화식과 직관적인 값의 초기화이다.

위 문제에서 점화식은 f(n) = f(n-2) + f(n-1) 이다. 또한 n = 1 일때와 2일때는 그 경우의 수를 쉽게 찾을 수 있다.

이렇게 점화식과 직관적인 값은 미리 입력해두고 풀면 너무 쉽게 풀 수 있는 것이 동적계획법이다.