[BOJ 9465] 스티커

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

9465번: 스티커

---

 

DP로 풀 수 있는 비교적 간단한 문제이다.

 

첫 번째 행의 스티커를 고르면 다음 열에서는 두 번째 행의 스티커를 골라야 하고

 

두 번째 행의 스티커를 고르면 다음 열에서는 첫 번째 행의 스티커를 골라야 한다.

 

즉, 각 행의 N번째 열까지의 최대값은 N-1번째까지의 각기 다른 행의 값에 N번째 스티커를 더한 거다.

 

DP[행 번호][N] = DP[다른 행][N-1] + sticker[행 번호][N]  이 된다.

 

하지만 위 값만으로는 정답을 얻을 수 없다.

 

위 경우는 모든 열에서 스티커를 1개씩 고르지만, 특정 열에서는 스티커를 고르지 않을 수도 있다.

 

이를 위해서 단순히 이전 열까지의 값만이 아닌 전전 열의 값도 사용한다.

 

이전 열에서 스티커를 안 고른다면 이전 열에서 두 행의 스티커 모두 선택할 수 있으므로 

 

1. 이전 열의 다른 행값

2. 두 개전 열의 첫 번째 행값

3. 두 개전 열의 두 번째 행값

 

위 3가지 경우 중 가장 큰 것에 현재 스티커 값을 더하면 된다.

 

---

#include <stdio.h>

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

int n;
int a[2][100001];

int dp[2][100001];

int main()
{
	int T;
	scanf("%d", &T);

	while (T--)
	{
		scanf("%d", &n);
		for (int j = 0; j < 2; j++)
			for (int i = 1; i <= n; i++)
				scanf("%d", &a[j][i]);

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

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