BOJ [9465] 스티커

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

1. 분류

다이나믹 프로그래밍

2. 풀이

전형적인 DP 문제 중 하나이다.

스티커의 조건을 잘 생각하고, 1열부터 5열까지 순차탐색으로 진행하면서 값을 찾을 방법을 생각해보았다.

한 스티커의 열 단위에서 행할 수 있는 동작은 3가지가 있다.

1. 아무 스티커도 건드리지 않는다.

2. 윗 줄의 스티커를 떼어낸다.

3. 아랫 줄의 스티커를 떼어낸다.

이 세 가지 동작을 세세하게 나눠보자면,

1. 아무 스티커도 건드리지 않을 때는 이전 단계에서 무엇을 하던간에 상관 없이 수행할 수 있다.

2. 이전 단계에서 윗 줄의 스티커를 떼어내지 않은 경우에만 가능하다.

3. 이전 단계에서 아랫 줄의 스티커를 떼어내지 않은 경우에만 가능하다.

이렇게만 알고 있으면 점화식을 작성할 수 있다.

1. 이번 단계에서 아무 스티커도 건드리지 않는 점화식

2. 이번 단계에서 윗 줄의 스티커를 떼어내는 점화식.

3. 이번 단계에서 아랫 줄의 스티커를 떼어내는 점화식

정답은 저 세 가지 값 중 가장 큰 것을 택하면 된다.

3. 소스코드

#include <cstdio>

#define max(a, b, c) (a) > (b) ? ((a) > (c) ? (a) : (c)) : ((b) > (c) ? (b) : (c))

int sticker[2][100000] = { 0 };
int dp[3][100000] = { 0 };
// [0] : 떼지 않음
// [1] : 현재 열의 위쪽 스티커를 뗌
// [2] : 현재 열의 아래쪽 스티커를 뗌

int main()
{
	int t;

	for(scanf("%d", &t); t > 0; t--)
	{
		int n;
		scanf("%d", &n);

		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < n; j++)
				scanf("%d", &sticker[i][j]);
		}

		dp[0][0] = 0;
		dp[1][0] = sticker[0][0];
		dp[2][0] = sticker[1][0];

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

		printf("%d\n", max(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]));
	}

	return 0;
}