백준 9465 스티커

Dp로 접근하기 시작한 것이 장족의 발전인것 같다. ㅑ호

 

이제 내 힘만으로 풀 수 있을 날이 곧 멀지 않았다!

 

대각선으로 덧셈하는 것 자체는 맞았지만, 대각선이나 혹은 한칸 더 가서 대각선와 비교해야됬는데... ㅠ

 

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <iostream>
using namespace std;

int main() {
	int n, a;

	int arr1[100002];
	int arr2[100002];
	int dp[2][100002];
	scanf("%d", &n);
	while (n-->0) {
		scanf("%d", &a);
		for (int i = 1; i <= a; i++) {
			scanf("%d", &arr1[i]);
		}
		for (int i = 1; i <= a; i++) {
			scanf("%d", &arr2[i]);
		}
		dp[0][0] = 0; dp[1][0] = 0;
		dp[0][1] = arr1[1], dp[1][1] = arr2[1];

		for (int i = 2; i <= a; i++) {
			dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + arr2[i];
			dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + arr1[i];
		}
		printf("%d\n", max(dp[0][a],dp[1][a]));
	



	}
	

}