9465_스티커

▶실버1

풀이

여기서 중요하게 봐야할 것은 두 변을 공유하지 않는다는 점이다. 이 점을 참고하여 배열을 arr[i][j], dp[i][j] 두 개 만든다.(i는행, j는 열)

① n = 1이라면,

50

10

dp[0][0]의 값은 50이며,

dp[1][0]의 값은 10이다.

② n = 2이라면,

50	10
30	50

dp[0][1]의 값은 dp[1][0] + arr[0][1] = 30 + 10 = 40

dp[1][1]의 값은 dp[0][0] + arr[1][1] = 50  + 50 = 100 이다.

③ n = 3이라면,

50	10	100
30	50	70

여기서부터 살짝 복잡해지는데, dp값이 두 가지 경우일 수 있다.

dp[0][2]의 값은 dp[1][1], dp[1][0]의 값 중 큰 값에 arr[0][2]을 더한 값이다.

dp[0][2] = max(dp[1][1], dp[1][0]) + arr[0][2] = 100 + 100 = 200

마찬가지로 dp[1][2] 의 값은 dp[0][1], dp[0][0]의 값 중 큰 값에 arr[1][2]을 더한 값이다.

dp[1][2] = max(dp[0][1], dp[0][0]) + arr[1][2] = 50 + 70 = 120

 

④ n = 4이라면,

50	10	100	20
30	50	70	10

앞선 규칙을 이용하여 구해보면

dp[0][3] = max(dp[1][2], dp[1][1]) + arr[0][2] = 120 + 20 = 140

dp[1][3] = max(dp[0][2], dp[0][1]) + arr[1][2] = 200 + 10 = 210

 

여기서 주의할 점은 현재 열인덱스(j) - 3의 dp값은 고려하지 않는다. (위의 경우에선 dp[0][0], dp[1][0]을 생각하지 않는다는 말)
왜냐하면 (j - 3) 인덱스의 dp값에 상관없이 (j - 2) 또는 (j - 1)인덱스의 값을 무조건 더할 수 있기 때문이다. 더할 값이 존재하는 경우는 생각하지 않는다.

 

이런 규칙을 이용하여 점화식을 나타내면

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

 

코드

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

int dp[2][100001];
int arr[2][100001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

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

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

	}
}