BaekJoon 9465번: 스티커(C++)

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

9465번: 스티커

풀이법

1) 단순 반복문으로는 시간 초과가 발생하기에 DP를 이용해서 푸는 문제이다.

2) 점화식을 세울 때, ans 배열 규칙을 찾아야 했다.

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

새로 갱신할 최대 값의 배열의 다른 행 중 어떤 값을 가져오는가가 핵심이다.

다른 행의 두 칸 전 값과 다른 행의 한 칸 전 값을 비교하여 더 큰 값에 현재 배열의 값을 더 해주면 점화식을 세워 문제를 해결할 수 있었다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int t;
int arr[2][100001];
int ans[2][100001];
int dp(int n)
{
	ans[0][0] = arr[0][0];
	ans[1][0] = arr[1][0];
	ans[0][1] = arr[1][0] + arr[0][1];
	ans[1][1] = arr[0][0] + arr[1][1];
	for (int i = 2; i < n; i++)
	{
		ans[0][i] = max(ans[1][i-2]+arr[0][i],ans[1][i-1]+arr[0][i]);
		ans[1][i] = max(ans[0][i - 2] + arr[1][i], ans[0][i - 1] + arr[1][i]);
	}
	return max(ans[0][n-1], ans[1][n-1]);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	for (int p = 0; p < t; p++)
	{
		int n;
		cin >> n;
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cin >> arr[i][j];
			}
		}
		int res=dp(n);
		cout << res << "\n";
	}
}