[BOJ/C++] 9465 스티커

문제

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

풀이

아래 규칙으로 점화식 만들면 됨 !

시작점이 첫 번째일 수도 있고, 두 번째 일 수도 있음 ➡️ DP에 0 0 넣어주고 시작
⚠️V랑 DP 범위 다름에 주의

코드

#include <iostream>
#include <vector>

using namespace std;

int dp[2][100001];

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n;
		vector<int> v[2];
		cin >> n;
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < n; j++) {
				int tmp;
				cin >> tmp;
				v[i].push_back(tmp);
			}
		}

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

		cout << max(dp[0][n], dp[1][n]) << '\n';
	}

	return 0;
}