백준 9465번 - 스티커(C++)

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

9465번: 스티커

 

2차원 DP문제이다. 이 문제를 지난학기에는 풀지 못했었는데 이번에 풀게 되어 기쁘다. 놀기만 한 건 아니라는 거지.. 아무튼, 2차원 dp배열을 선언하고 풀이하면 된다. 이 문제는 bottom up 방식으로 먼저 왼쪽부터 오른쪽으로 진행하며 풀이를 했다. 오른쪽에서 왼쪽으로 가도 상관은 없다.

 

- 접근법

 이 문제를 재귀나 분기로 풀면 어떻게 될까. 만약 0,0 을 선택했을 때 다음으로 스티커를 선택할 수 있는 가지수는 이웃한 두개와 본인을 제외하면 N - 3이다. 그러므로 시간복잡도가 너무 높아진다. 그러므로 dp가 필요하다.

 

dp[i][j] = 이 스티커를 뗐을 때 가장 높은 점수

 

초기 세팅을 생각하면 다음과 같다. 

위 네개의 좌표는 언제나 저 최댓값을 갖는다.

 

그리고 0, 2 스티커를 보자. 이 스티커를 뗐을 때 0,0 1,0 1, 1 세개의 선택지가 있다. 그러므로 이 세개의 dp중 가장 큰 것을 선택하면 된다. 이렇게 bottom 부터 만들어가며 top까지 도달한다. 

 

dp[0][a] = board[0][a] + max(dp[0][a - 2], dp[1][a - 2], dp[1][a - 1])

 

위의 식을 찾아냈다면 이제 정답을 도출할 수 있다.

 

#include <iostream>

using namespace std;

int board[2][100001];
int dp[2][100001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int T, N;

	cin >> T;

	for (int i = 0; i < T; i++) {
		
		cin >> N;

		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < N; k++) {
				cin >> board[j][k];
			}
		}

		dp[0][0] = board[0][0];
		dp[0][1] = board[0][1] + board[1][0];
		dp[1][0] = board[1][0];
		dp[1][1] = board[0][0] + board[1][1];

		for (int a = 2; a < N; a++) {
			dp[0][a] = board[0][a] + max(max(dp[0][a - 2], dp[1][a - 2]), dp[1][a - 1]);
			dp[1][a] = board[1][a] + max(max(dp[1][a - 2], dp[0][a - 2]), dp[0][a - 1]);
		}

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