[BOJ 9465] 스티커

문제 출저 : https://www.acmicpc.net/problem/9465

 

풀이 :

 

DP문제입니다.

 

스티커를 떼면 변을 공유하는 모든 스티커는 사용 할 수 없으니 대각선 스티커만 보면 됩니다.

아래의 그림에서 60점 스티커를 뗀다고 가정했을때,

그 전에 점수를 쌓을 수 있는 경우는 20점과 100점을 뗐을 때 뿐입니다.

그럼 20점을 뗀다면 어떨까요?

그 전에 점수를 쌓을 수 있는 경우는 70점과 50점을 뗐을 때 뿐이겠죠.

따라서 쌓는 과정에서 값의 틀어짐이 없이 잘 쌓일 거라는 사실을 알 수 있습니다.

문제의 목표는 스티커 점수의 최댓값을 찾는 것이므로 두가지 경우 중 값이 더 큰 경우를 채택하면 됩니다.

 

#include<stdio.h>
 
int t,n, arr[2][100000];
 
int main()
{
    scanf("%d", &t);
    for (int test = 0; test < t; test++)
    {
        scanf("%d", &n);
        for (int inp = 0; inp < 2; inp++)for (int inp1 = 0; inp1 < n; inp1++)scanf("%d", &arr[inp][inp1]);
        arr[0][1] += arr[1][0];
        arr[1][1] += arr[0][0];
        for (int i = 2; i < n; i++)
        {
            arr[0][i] += arr[1][i - 1] > arr[1][i - 2] ? arr[1][i - 1] : arr[1][i - 2];
            arr[1][i] += arr[0][i - 1] > arr[0][i - 2] ? arr[0][i - 1] : arr[0][i - 2];
        }
    printf("%d\n",(arr[0][n - 1] > arr[1][n - 1] ? arr[0][n - 1] : arr[1][n - 1]));
    }
}