백준] 9465 - 스티커(ACM-ICPC Regionals)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

소스코드

#include <iostream>
#include <vector>
using namespace std;
int max(int a, int b)
{
	return a < b ? b : a;
}
int main(void)
{
	int t, n, ans;
	cin >> t;
	while (t--)
	{
		vector<vector<int> > arr(2), dp(2);
		cin >> n;
		for (int i = 0; i < 2; i++)
		{
			arr[i] = vector<int>(n+1, 0);
			dp[i] = vector<int>(n+1, 0);
		}
		for (int i = 0; i < 2; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				cin >> arr[i][j];
				dp[i][j] = arr[i][j];
			}
		}

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

Tip

동적계획법 문제로, 2차원 배열을 그려서 어떤 경우가 존재하는지 따져보면 수월하게 풀 수 있다. 스티커를 하나 선택하면 상하좌우는 선택할 수 없고, 대각선 방향만 선택이 가능한데, 대각선 방향은 물론이고 대각선의 옆 방향도 선택할 수 있다는 점을 고려해야 한다.

dp[0][i] = dp[0][i] + max(dp[1][i - 1], dp[1][i - 2]);

dp[1][i] = dp[1][i] + max(dp[0][i - 1], dp[0][i - 2]);