92. 네트워크 선 자르기(동적계획법_ Top-Down : 재귀, 메모이제이션) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include <iostream>

using namespace std;

int dy[50];

int DFS(int x)
{
	if(x == 1)
	{
		dy[x] = 1;
		return dy[x];
	}
	if(x == 2)
	{
		dy[x] = 2;
		return dy[x];
	}
	else
	{
		if(dy[x] != 0)
		{
			return dy[x];
		}
		else
		{
			return dy[x] = DFS(x-2) + DFS(x-1);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	DFS(n);
	
	cout << dy[n] << "\n";
	return 0;
}

1. 메모이제이션은 쉽게 말하면 이미 연산해서 나온 값을 어떤 배열에 저장해놓고 필요할 때 가져와서 쓰는 것이다.

재귀함수의 치명적인 단점을 매우 보완해줄 수 있는 방법이다.