[boj 9465/c++] 스티커(동적계획법, dp)

동적계획법(dynamic programming, dp)는 큰 문제를 작은 문제로 나누어서 푸는 방법을 일컫는 말이다.

분할정복(Divide and Conquer)와 비슷하지만 분할정복은 큰문제를 작은 문제로 나누어 해결하고 나누어진 작은 해결법들을 다시 합쳐가면서(작은 문제에서 반복이 일어나지 않음) 문제를 해결하고, 동적계획법은 작은 부분문제들이 답이 바뀌지 않고 같은 값을 가지며 큰 문제를 해결해 나가는 것에 차이가 있다.

 

반복되는 규칙(점화식)을 가지고 문제를 풀어나가는 경우가 많으며

작은 수부터 차례로 접근하며 규칙을 찾아 이를 해결해야한다.

 

구현법은 bottom-up과 top-down 방식이 있는데, bottom-up은 반복문을 통해 처음부터 문제를 풀어나가고, top-down방식은 재귀함수를 통해 큰 문제를 더 작은 문제로 나눠나간다.

 

https://www.acmicpc.net/problem/9465

9465번: 스티커

스티커 문제도 동적계획법을 이용하는 문제 중 하나로

문제를 해결하면서 중요한 키포인트는 하나의 스티커를 사용하면 위,아래, 양 옆 스티커를 사용할 수 없다는 점을 어떻게 구현할 것인가 였다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
using namespace std;

void bottomUp(int n) {
	int** dp = new int* [2];
	dp[0] = new int[n+1];
	dp[1] = new int[n+1];
	dp[0][0] = dp[1][0] = 0;

	for (int i = 1; i <= n; i++) {
		cin >> dp[0][i];
	}

	for (int i = 1; i <= n; i++) {
		cin >> dp[1][i];
	}
	for (int i = 2; i <= n; i++) {
		dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + dp[0][i];
		dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + dp[1][i];
	}
	int answer = max(dp[1][n], dp[0][n]);
	cout << answer << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int tcase;
	cin >> tcase;
	while (tcase--) {
		int n;
		cin >> n;
		bottomUp(n);
	}
}