스티커 (feat. 백준, 9465번)

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

9465번: 스티커

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/9465
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int T, N, arr[100001][2], dp[100001][2] = { 0 };
	cin >> T;
	for (register int t = 1; t <= T; ++t) {
		cin >> N;
		for (register int iy = 0, ix; iy < 2; ++iy)
			for (ix = 1; ix <= N; ++ix)
				cin >> arr[ix][iy], dp[ix][iy] = 0;
		dp[0][0] = dp[0][1] = 0, dp[1][0] = arr[1][0], dp[1][1] = arr[1][1];
		for (register int i = 2; i <= N; ++i) {
			dp[i][0] = max(dp[i - 1][1], dp[i - 2][1]) + arr[i][0];
			dp[i][1] = max(dp[i - 1][0], dp[i - 2][0]) + arr[i][1];
		}
		cout << *max_element(dp[1], dp[1 + N]) << endl;
	}
	return 0;
}
// *&)*@*

1. 인접한 면의 스티커를 사용할 수 없다는 것은 현재 기준 이전의 대각선 방향을 선택할 수 있다는 것입니다.
2. 문제의 예로 주어졌듯이, 100의 스티커 다음이 70의 스티커였고, 따라서 이전의 대각선 방향과 그 전의 스티커를 취하는 경우를 가장 큰 경우로 보았습니다.
3. 따라서 현재의 스티커를 Ai0, Ai1 이라고 했을때, DPi0 = max(DPi-11, DPi-21) + Ai0 (단, i >= 2인 경우) 의 식이 성립됩니다. (DPi1 도 마찬가지입니다.)
4. 따라서 DP10 ~ DPn1 까지 중 가장 큰값이 정답이 됩니다.