[개념] 네트워크 선 자르기(Top-Down, 재귀, 메모이제이션) / c++ & c / 제한시간 없음

▣ 문제

현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면

의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다.

그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요?

 

▣ 입력설명

- 첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.

 

▣ 출력설명

- 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

 

▣ 입력 예시

7

 

▣ 출력 예시

21

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>
using namespace std;

int dy[101];

int dfs(int n) {
	if (dy[n] != 0) return dy[n];
	if (n == 1 || n == 2) return n;
	else {
		return dy[n] = dfs(n - 1) + dfs(n - 2);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	printf("%d\n", dfs(n));

	return 0;
}

동적계획법(Dynamic Programming)은 Top-Down 형식으로도 문제를 해결할 수 있다.

 

Top-Down 방식으로 풀기 위해서는 재귀와 메모이제이션을 이용한다.

 

Bottom-Up에서는 제일 큰 문제에서 작은 문제로 나눠서 푸는 방식이다.

 

입력 예시를 예로 들어서 7M짜리 선을 먼저 생각해보면

 

제일 끝부분이 1M일떄 또는 2M일때로 나눠보면

 

		남은길이(6M)
		남은길이(5M)

가 될것이다.

 

이제 DFS함수를 사용해 6M짜리와 5M짜리도 계속해서 나눠준다.

 

DFS 결과

이때 중요 포인트는 D(1)와 D(2)를 통해 얻은 D(3)를 dy[ ]에 저장을 해줌으로써 다음 탐색을 할때 재사용을 할수 있게끔 해주는 방식이다(if (dy[n] != 0) return dy[n];).

 

이것이 메모이제이션이라 하고 이를 통해 시간을 훨씬 단축할 수 있다.