백준 - 9465번 : 스티커 (C++)

풀이 방법 : DP

점수의 합이 최대가 되도록 스티커를 떼어내야 하는 문제
하나의 스티커를 뜯게 되면 뜯은 스티커와 변을 하나라도 공유하는 스티커는 뜯을 수 없다.

왼쪽에서부터 차례대로 스티커를 뜯어간다고 생각하고 각 인덱스의 스티커를 뜯을 수 있는 경우 중 최댓값을 구해서 갱신해나가면 된다.

#include <iostream>
#include <vector>

using namespace std;

int DP[2][100001] = {};

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int T;
	cin >> T;

	while (T > 0)
	{
		--T;

		int N;
		cin >> N;
		
		vector<vector<int>> vecScore(2);

		for (int i = 0; i < 2; ++i)
		{
			vecScore[i].resize(N);
			for (int j = 0; j < N; ++j)
			{
				cin >> vecScore[i][j];
				DP[i][j] = -1;
			}
		}

		DP[0][0] = vecScore[0][0];
		DP[1][0] = vecScore[1][0];
		DP[0][1] = DP[1][0] + vecScore[0][1];
		DP[1][1] = DP[0][0] + vecScore[1][1];

		for (int i = 2; i < N; ++i)
		{
			DP[0][i] = max(DP[0][i - 2], DP[1][i - 2]);
			DP[0][i] = max(DP[0][i], DP[1][i - 1]);
			DP[0][i] += vecScore[0][i];

			DP[1][i] = max(DP[0][i - 2], DP[1][i - 2]);
			DP[1][i] = max(DP[1][i], DP[0][i - 1]);
			DP[1][i] += vecScore[1][i];
		}

		int MaxScore = max(DP[0][N - 1], DP[1][N - 1]);
		cout << MaxScore << '\n';

	}
}