[BOJ/C++]9465(스티커)

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

• 점화식부터 차근히 풀자는 생각이 정말 좋았다. 문제 보고 구조 확실하게 짜고 푸는 습관을 들이자.

1. 점수의 합이 최대가 되게 -> 누적 합 예상(DP, SegTree)
2. 2행 n열 -> SegTree 문제를 굳이 다차원에서 풀라고 하진 않을 것 같았음(최소한 그 정도 난이도는 아니라고 판단)

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 100000
int n;
int dp[2][MAX]{ 0 };
int area[2][MAX];

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> area[0][i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> area[1][i];
	}
}

void solution() {
	input();
	for (int i = 1; i <= n; ++i) {
		dp[0][i] = max(dp[1][i - 1] + area[1][i - 1], dp[0][i - 1]);
		dp[1][i] = max(dp[0][i - 1] + area[0][i - 1], dp[1][i - 1]);
	}
	cout << max(dp[0][n], dp[1][n]) << '\n';
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		solution();
	}
	return 0;
}