[BAEKJOON] 9465 스티커

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; //vector<vector<int>> sticker(2, vector<int>(100010)); //vector<vector<int>> DP(2, vector<int>(100010)); int main() { int for_count, sticker_count; scanf("%d", &for_count); for (int i = 0; i < for_count; i++) { scanf("%d", &sticker_count); vector<vector<int>> sticker(2, vector<int>(100010,0)); vector<vector<int>> DP(2, vector<int>(100010,0)); for (int k = 0; k < 2; k++) for (int n = 2; n < sticker_count+2; n++) scanf("%d", &sticker[k][n]); //1. 대각선 아래 //2. 대각선 아래 왼쪽 //3. 선택하지 않았을 때 for (int k = 2; k < sticker_count+2; k++) { DP[0][k] = max(max(DP[1][k - 2], DP[1][k - 1]) + sticker[0][k], DP[0][k - 1]); DP[1][k] = max(max(DP[0][k - 2], DP[0][k - 1]) + sticker[1][k], DP[1][k - 1]); } printf("%d\n", max(DP[0][sticker_count+1], DP[1][sticker_count+1])); } return 0; }