[BOJ] #9465 _ 스티커

[스티커] https://www.acmicpc.net/problem/9465

9465번: 스티커

아주 간단한 DP문제이다.

100점인 스티커를 기준으로 가능한 경우는 아래와 같이 3가지다.

 

이를 이용하여 점화식을 만들 수 있다.

점화식을 만들기 위해 우선,

1번째 줄에서 시작하는 경우와 2번째 줄에서 시작하는 경우로 나누어 생각해야 한다.

 

- dp[0][0] = sticker[0][0] (1번째 줄 기준, n=1)
- dp[1][0] = sticker[1][0] (2번째 줄 기준, n=1)
- dp[0][1] = max(dp[0][0], dp[1][0] + sticker[0][1]) (1번째 줄 기준, n=2) 
- dp[1][1] = max(dp[1][0], dp[0][0] + sticker[1][1]) (2번째 줄 기준, n=2)
- dp[0][n] = max(dp[0][n - 1], max(dp[1][n - 1] + sticker[0][n], dp[1][n - 2] + sticker[0][n])) (n>2)
- dp[1][n] = max(dp[1][n - 1], max(dp[0][n - 1] + sticker[1][n], dp[0][n - 2] + sticker[1][n])) (n>2)

 

점화식을 이용하여 다음과 같이 소스를 짤 수 있다.

 

[ 소스 코드 ]

#include <cstdio>
#include <algorithm>
#define MAX 100000

using namespace std;

int sticker[2][MAX + 1] = { 0, }, dp[2][MAX + 1] = { 0, };
int n;

void solve();
void init_arr();
int main() {
	int T;

	scanf("%d", &T); //Input
	for (int i = 0; i < T; i++) {
		scanf("%d", &n);
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < n; k++) scanf("%d", &sticker[j][k]);
		}
		solve();
		printf("%d\n", max(dp[0][n - 1], dp[1][n - 1]));
		init_arr();
	}
	return 0;
}

void solve() {
	dp[0][0] = sticker[0][0]; //init
	dp[1][0] = sticker[1][0];
	dp[0][1] = max(dp[0][0], dp[1][0] + sticker[0][1]);
	dp[1][1] = max(dp[1][0], dp[0][0] + sticker[1][1]);

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

void init_arr() {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < n; j++) dp[i][j] = 0;
	}
}