백준 9465번: 스티커

[문제 링크]

9465번: 스티커

---

길이가 2 x n 인 스티커에서 최대 점수를 구하는 방법은 다음과 같다.

 

max(d[0][n], d[1][n])

 

즉, 마지막줄에서 위에 칸을 떼어냈을 때 얻을 수 있는 최대값 vs 마지막줄에서 아래 칸을 떼어냈을 때 얻을 수 있는 최대값 중 더 큰값이 최대 점수가 된다.

 

n열에서 1행을 떼어냈을 때와 2행을 떼어냈을 때 얻을 수 있는 최대값을 구하는 점화식은 다음과 같이 나타낼 수 있다.

 

dp(0, n) = max(dp(1, n-1) + score[0][n], dp(1, n-2) + score[0][n])

dp(1, n) = max(dp(0, n-1) + score[1][n], dp(0, n-2) + score[1][n])

 

위 점화식을 구현하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
#include <cstring>
using namespace std;

int P[2][100000], memo[2][100000];

inline int max(int a, int b) { return a > b ? a : b; }

int Topdown(int y, int x)
{
	if (x < 0) return 0;

	int& ret = memo[y][x];
	if (ret != -1) return ret;

	if (y == 0) return ret = max(Topdown(1, x - 1), Topdown(1, x - 2)) + P[0][x];
	if (y == 1) return ret = max(Topdown(0, x - 1), Topdown(0, x - 2)) + P[1][x];
}

int Bottomup(int n)
{
	memo[0][0] = P[0][0];
	memo[1][0] = P[1][0];
	memo[0][1] = memo[1][0] + P[0][1];
	memo[1][1] = memo[0][0] + P[1][1];

	for (int i = 2; i < n; i++)
	{
		memo[0][i] = max(memo[1][i - 1], memo[1][i - 2]) + P[0][i];
		memo[1][i] = max(memo[0][i - 1], memo[0][i - 2]) + P[1][i];
	}

	return max(memo[0][n - 1], memo[1][n - 1]);
}
int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		int n;
		cin >> n;
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < n; j++)
				cin >> P[i][j];

		// top-down
		cout << "top-down: " << max(Topdown(0, n - 1), Topdown(1, n - 1)) << endl;

		// bottom-up
		cout << "bottom-up: " << Bottomup(n) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 72 day