백준 9465

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

다이나믹 프로그래밍.. 어떤 개념인지 아직도 헷갈린다 ㅠㅠ
기존 배열을 기반으로 새로운 배열을 만들고 거기다가 점화식 대입해서 푸는 것 같은데, 아직 더 공부할 게 많은가보다..

알고리즘 설명은 이 블로그에 잘 설명되어 있다.
https://m.blog.naver.com/occidere/220786307316

역시나 점화식을 찾는게 중요한 것 같다.

제출한 코드 :

#define _CRT_SECURE_NO_WARNINGS
#define MAX(a,b)((a>b)? (a):(b))

int arr[2][100000];
int dp[2][100000];

#include <stdio.h>

int main() {
	int n, t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%d", &arr[0][i]);
		}
		for (int i = 0; i < n; i++) {
			scanf("%d", &arr[1][i]);
		}
		dp[0][0] = dp[1][0] = 0;
		dp[0][1] = arr[0][0];
		dp[1][1] = arr[1][0];
		for (int i = 2; i <= n; i++) {
			dp[0][i] = MAX(dp[1][i - 2], dp[1][i - 1]) + arr[0][i-1];
			dp[1][i] = MAX(dp[0][i - 2], dp[0][i - 1]) + arr[1][i-1];
		}
		printf("%d\n", MAX(dp[0][n], dp[1][n]));
	}
	return 0;
}