[C++] 백준 9465번: 스티커

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

9465번: 스티커

풀이과정

\(i\)번째 열까지의 최대값을 차례로 찾는 것이 관건이다. 

위와 아래의 스티커 중 어떤 것을 선택하는 것이 이후에 최대값을 만드는데 유리한지 모르므로, 각 경우에 따라 최대값을 저장해야 한다.

\(i\)번째 열까지의 최대값을 구하면 아래와 같다.

\(\text{if i is 0 then, }\)

\(\text{        }score[i][0] = sticker[0][0]\)

\(\text{        }score[i][1] = sticker[0][1]\)

\(\text{if i is 1 then, }\)

\(\text{        }score[i][0] = sticker[0][1] + sticker[1][0]\)

\(\text{        }score[i][1] = sticker[0][0] + sticker[1][1]\)

\(\text{for every 1 < i < N, }\)

\(\text{        }score[i][0] = max(score[i - 1][1] + sticker[i][0], score[i - 2][1] + sticker[i][0])\)

\(\text{        }score[i][1] = max(score[i - 1][0] + sticker[i][1], score[i - 2][0] + sticker[i][1])\)

\(sticker[i][j]\)는 \(i\)번째 열의 \(j\)번째 행의 스티커 점수를 뜻하며, \(score[i][j]\)는 \(i\)번째 열의 \(j\)번째 행의 스티커를 선택할 때 얻을 수 있는 최대값을 뜻한다.

0번째 열에서는 각 스티커 하나를 선택하는 것이 최대값이다.

1번째 열에서는 0번째에서 다른 행의 스티커를 같이 선택하는 것이 최대값이다.

이후의 열에서는 이전 열에서 다른 행의 스티커를 같이 선택하거나, 이전 열에서 선택하지 않고 그 전 열에서 같은 행의 스티커를 선택한 경우 중 최대값을 고르면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	TC(T) {
		int N;
		cin >> N;
		vector<int[2]> sticker(N);
		FOR(i, 2) FOR(j, N)
			cin >> sticker[j][i];

		vector<int[2]> score(N);
		score[0][0] = sticker[0][0];
		score[0][1] = sticker[0][1];
		score[1][0] = sticker[0][1] + sticker[1][0];
		score[1][1] = sticker[0][0] + sticker[1][1];
		for (int i = 2; i < N; ++i) {
			score[i][0] = max(score[i - 1][1] + sticker[i][0], score[i - 2][1] + sticker[i][0]);
			score[i][1] = max(score[i - 1][0] + sticker[i][1], score[i - 2][0] + sticker[i][1]);
		}

		cout << max(score.back()[0], score.back()[1]) << EL;

	}

	return 0;
}