(c++)백준 9465번: 스티커

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

9465번: 스티커

만약 처음에 (1,1)위치의 스티커를 고르면 다음 스티커로 (2,2)위치의 스티커를 고를지, (2,3)위치의 스티커를 고를지 골라야 한다. ∵(2,2)위치의 스티커를 고르면 (2,3)위치의 스티거를 고를 수 없게 되므로 더 큰 점수를 갖는 스티커를 고르는 게 유리!

v
	?	?

 

(1,3)위치의 스티커는 여기서 고려하지 않아도 된다. 만약 (1,3)을 선택할 거라면 (2,2)를 이미 선택했어야 최대가 될 수 있다.

v		v
	v

 

☆마지막 열부터 dp 쌓아가기☆

 

※점화식※ (S : 각 스티커의 점수 저장한 배열)

dp[1][n] = S[1][n]

dp[2][n] = S[2][n]

dp[i][j] : 뒤에서부터 골랐을 때, (i, j)위치의 스티커를 선택하면 가지게 되는 최대 점수

dp[1][x] = max(dp[2][x+1], dp[2][x+2]) + S[1][x]

dp[2][x] = max(dp[1][x+1], dp[1][x+2]) + S[2][x]

 

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

int T, n;
long long dp[3][100001];
int S[3][100001];

void DP() {
	dp[1][n] = S[1][n];
	dp[2][n] = S[2][n];
	dp[1][n - 1] = dp[2][n] + S[1][n - 1];
	dp[2][n - 1] = dp[1][n] + S[2][n - 1];

	//최댓값 만드는 것이기 때문에 첫번째 열과 마지막 열에서 숫자 하나씩은 꼭 골라야함
	for (int i = n - 2; i >= 1; i--) {
		dp[1][i] = max(dp[2][i + 1], dp[2][i + 2]) + S[1][i];
		dp[2][i] = max(dp[1][i + 1], dp[1][i + 2]) + S[2][i];
	}

	if (dp[1][1] > dp[2][1])
		cout << dp[1][1] << endl;
	else
		cout << dp[2][1] << endl;
}

int main() {
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> S[i][j];
			}
		}
		DP();
	}
	return 0;
}