[Silver 1] 9465번 스티커

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

9465번: 스티커

 

이 문제는 DP를 통해 해결할 수 있다.

 

알고리즘은 다음과 같다.

• 2N개의 데이터를 삽입시켜야 하므로 2차원 배열을 사용했다.
• DP배열도 2N만큼 생성한다.
• 0번 줄의 0번째 스티커와 1번 줄의 0번째 스티커는 (0,0) (1,0)의 값을 그대로 삽입한다.
• 0번 줄의 1번째 스티커와 1번 줄의 경로를 누적한다.
• 2번째 스티커부터 같은 패턴으로 경로가 누적된다.
  • i-2 전의 경로와 i-1번째 전 경로, 0번째 인 경우 1번째의 i-1번째 경로로 누적

 

#include <iostream>
#include<cstring>
using namespace std;
int T, N, result = 0;
int arr[2][100001] = { 0, };
int dp[2][100001] = { 0, };


int main() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		result = 0;
		memset(dp, 0, sizeof(dp));
		memset(arr, 0, sizeof(arr));
		cin >> N;
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < N; k++) {
				cin >> arr[j][k];
			}
		}
		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];
		result = max(max(dp[0][0], dp[1][0]), max(dp[0][1], dp[1][1]));

		for (int j = 2; j < N; j++) {
			dp[0][j] = max(dp[1][j - 2] + arr[0][j], max(dp[1][j - 1] + arr[0][j], dp[0][j - 2] + arr[0][j]));
			dp[1][j] = max(dp[0][j - 2] + arr[1][j], max(dp[0][j - 1] + arr[1][j], dp[1][j - 2] + arr[1][j]));
			result = max(result, max(dp[0][j], dp[1][j]));
		}
		cout << result << '\n';
	}
}