[백준/C++] 9465 스티커

유형	난이도	완료일	링크	특이사항
DP	실버1	23.4.9	https://www.acmicpc.net/problem/9465

 

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

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

int main(void)
{
	int t, n;
	cin >> t;
	for(int i=0; i<t; i++)
	{
		
		cin >> n;
		
		for(int  j= 0; j<n; j++)
		{
			cin >> arr[0][j];
		}
		for(int  j= 0; j<n; j++)
		{
			cin >> arr[1][j];
		}		
		
		dp[0][0] = arr[0][0];
		dp[1][0] = arr[1][0];
			
		dp[0][1] = arr[1][0] + arr[0][1];
		dp[1][1] = arr[0][0] + arr[1][1];
		
		for(int i=2 ; i<n; i++)
		{
			dp[0][i] = max(dp[1][i-2] + arr[0][i], dp[1][i-1] + arr[0][i]);
			dp[1][i] = max(dp[0][i-2] + arr[1][i], dp[0][i-1] + arr[1][i]);
		}
		
		cout<<max(dp[0][n-1], dp[1][n-1])<<"\\n";
	}
}

  두 줄의 배열을 채워나가는 DP문제로 n번째 칸에 선택지가 네 개 있다는 생각을 기반으로 점화식을 세울 수 있었다. n-1을 비우고 n-2까지의 최대합과 n 조합 2가지와 n-1까지의 최대합과 n 조합 2가지로 총 네 가지다. n-1번째 칸을 비우는 선택지를 생각해내는게 중요했던 것 같다.