[Baekjoon] 9465번: 스티커

🥅 문제

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

 

🔍 설계

처음에 전 열에서 어떤 행을 사용했는지에 따라 큐에 추가하는 방식을 사용하려고 생각해보았는데, 2^100000으로 시간 초과가 발생할 것으로 생각되어 제외하였다.

 

쉽게 다이나믹 프로그래밍을 이용하여 해결할 수 있다. 현재 열에서 0행을 사용할 것이라면, 전 열에서는 1행 또는 아무것도 사용하지 않았을 때의 값 중 최댓값에 더해야 한다. 아무 것도 사용하지 않았을 때는 인덱스 2에 저장하였다. 현재 열에서 1행을 사용할 것이라면, 전 열에서는 0행 또는 아무것도 사용하지 않았을 때의 값 중 최댓값에 더해야 한다  현재 열에서 아무것도 사용하지 않을 것이라면, 전 열에서 0행을 사용을 사용했을 때와 1행을 사용했을 때 중 큰 값을 저장하면 된다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int t, n;
vector<vector<int>> stickers(2, vector<int>(100000));
vector<vector<int>> dp(100000, vector<int>(3));

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> t;
	for (int k = 0; k < t; k++) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> stickers[0][i];
		}
		for (int i = 0; i < n; i++) {
			cin >> stickers[1][i];
		}

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

		int result = 0;
		for (int i = 0; i < 3; i++) {
			result = max(result, dp[n - 1][i]);
		}
		cout << result << "\n";

	}
	
	return 0;
}