[개념] 네트워크 선 자르기(Bottom-Up, DP) / 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[50];
int main() {
	int n;
	scanf("%d", &n);
	dy[1] = 1;
	dy[2] = 2;
	for (int i = 3; i <= n; i++) {
		dy[i] = dy[i - 1] + dy[i - 2];
	}
	printf("%d\n", dy[n]);

	return 0;
}

동적계획법(Dynamic Programming)이란 하나의 문제를 해결할 때 작은 문제를 큰 문제로 분할한 후 작은 문제를 해결한 결과를 저장해 큰 문제의 결과와 합치는 방식이다.

 

고등학교 수학에서 점화식을 생각하면 될것같다.

 

위 코드는 Bottom-Up 방식으로 문제를 풀었다.

 

Bottom-Up 방식은 문제에서 직관적으로 풀 수 있는 작은 문제를 푼다. 이를 통해 얻은 결과값으로 점화식을 세운후 반복문을 통해서 큰 문제로 확장시키는 것이다.

 

문제에서 선은 1m 또는 2m의 길이로 자른다고 한다. 그렇다면 1m의 선을 자를수 있는 방법은 1가지 2m의 선을 자를수 있는 방법은 2가지다 된다.

 

이러한 직관적인 결과를 구한 후 3m 짜리 선을 생각해보면 네트워크 선 제일 끝부분을 기준으로 1m를 이미 잘랐다고 가정한다.

 

남은 선 길이 (2M)

 

남은 선 길이 2M는 이전에 2가지 방법이 있다는점을 이용한다.

 

다음으로 네트워크 선 제일 끝부분 2M를 잘랐다고 가정한다.

 

남은 선 길이 (1M)

 

남은 선 길이 1M는 이전에 1가지 방법이 있다는 점을 이용한다.

 

결과적으로 3M 짜리 선의 가지수 = 2M 짜리 선의 가지수 + 1M 짜리 선의 가지수 라는 것을 알수있다.

 

이를 통해 점화식을 구하면 f(n) = f(n-1) + f(n-2) 를 알 수 있다.