[C++] 네트워크 선 자르기(DP, Bottom-Up, Top-Down) ⭐

📄문제

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

1) 1m+1m+1m+1m
2) 2m+1m+1m
3) 1m+2m+1m
4) 1m+1m+2m
5) 2m+2m

 

의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다.
그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법이 있는지 구하시오.

 

⬇️ 입력

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

7

 

⬆️ 출력

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

21

 

📝 풀이

#include <iostream>
using namespace std;

static int dy[46];

int main()
{
	ios_base::sync_with_stdio(false);

	int n;

	dy[1] = 1;
	dy[2] = 2;

	for (int i = 3; i <= 45; ++i)
		dy[i] = dy[i - 1] + dy[i - 2];

	cin >> n;
	cout << dy[n];
}

• dp를 이용하여 이전 계산 값을 저장하고, 하나씩 쌓아 올라가는 bottom-up 방식으로 계산하였습니다.
• 네트워크 선은 1m일때 1m 방법 1개, 2m일때 1m x 2와 2m x 1로 총 2가지의 방법이 있습니다.
• 3m인 경우에는, 1m + 2m와 2m + 1m의 방법 두가지로 구현이 가능합니다.
• 즉, 점화식은 N = N - 1 + N - 2로 답을 구할 수 있습니다.

 

#include <iostream>
using namespace std;

int dp[46];

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

int main()
{
	ios_base::sync_with_stdio(false);

	dp[1] = 1;
	dp[2] = 2;

	int n;
	cin >> n;
	cout << DFS(n);
}

• top-down 방식은 bottom-up 방식과 반대로, 위에서부터 해결하는 방법을 사용합니다.
• 보통 재귀를 사용하여, dp에 저장된 값을 이용하여 해결할 수 있습니다.
• 점화식은 bottom-up 방식과 동일합니다.