[백준] C++ 9465번(스티커)

#include <iostream>

using namespace std;

int main(void)
{
	int a=0;
	
	cin>>a;
	
	for(int l=0; l<a; l++)
	{
		int n=0;
		cin>>n;
		
		int arr[2][100001]={0};
		int DP[2][100001]={0};
		
		for(int i=0; i<2; i++)
		{
			for(int j=0; j<n; j++)
			{
				cin>>arr[i][j];
			}
		}
		
		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];
		
		int max=0;
		
		for(int i=0; i<2; i++)
		{
			for(int j=0; j<2; j++)
			{
				if(DP[i][j]>max)
				{
					max=DP[i][j];
				}
			}
		}
		
		
		
		
		for(int i=2; i<n; i++)
		{
			if(DP[0][i-2]>DP[0][i-1])
			{
				DP[1][i]=arr[1][i]+DP[0][i-2];
			}
			else
			{
				DP[1][i]=arr[1][i]+DP[0][i-1];
			}
			
			if(DP[1][i-2]>DP[1][i-1])
			{
				DP[0][i]=arr[0][i]+DP[1][i-2];
			}
			else
			{
				DP[0][i]=arr[0][i]+DP[1][i-1];
			}
		
		}
		if(DP[0][n-1]>max)
		{
			max=DP[0][n-1];
		}
		if(DP[1][n-1]>max)
		{
			max=DP[1][n-1];
		}
		
		cout<<max<<'\n';
	}
	
	
	return 0;
}

 

스티커는 두 변을 공유하지 않는 스티커 점수의 최댓값을 구하라.

일단 예제를 살펴보자.

예제에서는 (50, 50, 100, 60)이 정답이라고 말하고 있다.

60을 기준으로 살펴보겠다.

 

60을 기준으로 살펴보았을 때 이전에 가능한 경우는 100이거나 20인 경우다 

왜 100과 20이 가능한 경우의 수냐??

일단 10은 인접해 있기 때문에 불가능하고, 20은 대각선에 있기 때문에 가능하다.

100을 왜 넣었냐?? 만약 100까지의 합이 20까지의 합보다 크다면 (20,10)을 뛰어넘는 것이 가능하다.

실제로 위 값은 100까지의 합이 20까지의 합보다 커서 100이 선택됨.

이러한 방법으로 스티커마다 가질 수 있는 최댓값을 계산해 주면 된다.