[백준 BOJ][C++]9465번 스티커 풀이: DP

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

9465번: 스티커

 

 

 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. 

 

 DP는 2차원 배열 dp[2][100001] 크기로 선언하였습니다. 2차원 배열 arr은 2n개의 스티커 점수를 나타내는 배열입니다.

 

 dp[0][n] = 1열부터 n-1열의 총 스티커 점수에 n열 0행을 더했을 때의 최대 점수이고

 dp[1][n] = 1열부터 n-1열의 총 스티커 점수에 n열 1행을 더했을 때의 최대 점수입니다. 

 

dp 초깃값으로 dp[0][0] = dp[1][0] = 0, dp[0][1] = arr[0][1], dp[1][1] = arr[1][1] 로 해줍니다. 

 

문제 예시를 살펴보겠습니다.

 

dp 1열은 초기화 해주었으니 2열부터 볼게요.

 

dp[0][2]의 값이 될 수 있는 것은 dp[1][0] + arr[0][2] 이거나 dp[1][1] + arr[0][2] 입니다.

즉 10 vs 40 이죠? 이 중 최댓값인 40을 dp[0][2]로 설정합니다.

 

dp[1][2]의 후보도 마찬가지로 dp[0][0] + arr[1][2] 또는 dp[0][1] + arr[1][2] 입니다.

50 vs 100 이므로 dp[1][2]의 값은 100이 됩니다. 

 

dp[0][3] 을 보겠습니다. dp[0][3]의 후보는 다음 표에서 파란색 수들의 합과 초록색 수 중 최댓값과 arr[0][3]을 더하면 됩니다. 

 

즉, n열의 0행 또는 1행 원소까지의 합은 n-1열까지의 합과 n-2열까지의 합 중 최댓값이 됩니다.

	0열	1열	2열	3열	4열	5열
0행	0	50	10	100	20	40
1행	0	30	50	70	10	60

 

점화식은 다음과 같습니다. 

 

dp[0][n] = max( dp[1][n-1], dp[1][n-2] ) + arr[0][n]

dp[1][n] = max( dp[0][n-1], dp[0][n-2] ) + arr[1][n]

 

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>

using namespace std;

int dp[2][100001] = { 0, };
int arr[2][100001];

int main(void) {

	int t, n;
	int ans;

	cin >> t;

	while (t > 0) {
		cin >> n;
		ans = 0;

		for (int i = 0; i < 2; i++) {
			for (int j = 1; j <= n; j++)
				cin >> arr[i][j];
		}

		dp[0][0] = dp[1][0] = 0;
		dp[0][1] = arr[0][1];
		dp[1][1] = arr[1][1];

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

		ans = max(dp[0][n], dp[1][n]);

		cout << ans << endl;

		t--;
	}
	

	return 0;
}