[DP] 스티커 문제 풀이

백준 9465번 스티커 문제 풀이 : https://www.acmicpc.net/problem/9465

문제요약 : 

- 2xn개의 스티커를 갖고있다. 각 스티커는 점수가 있다.

- 스티커를 떼면 그 스티커와 변을 공유하는 스티커는 찢어져 사용할 수 없다(점수x)

- 뗄 수 있는 스티커 점수의 최댓값을 구하시오.

우선 이런 유형의 문제는 완전탐색을 하여 구현을 해봅니다.. 그다음 DP를 적용..

1. 완전탐색을 할 경우를 생각해봅니다.

 "-->" 오른쪽 방향으로 탐색을 했을 때, 

스티커를 떼는 방법은 위를 떼는 방법, 그리고 아래를 떼는 방법 두가지가 존재합니다.

 우선 공유하는 변의 스티커가 뜯어지는 경우를 무시하고 전체 경우를 구한다면, 아래와 같이 구현할 수 있습니다.

int solve(int x)
{
    if (x >= n) return 0;
    int ret1 = solve(x + 1) + score[0][x];//위의 스티커를 뗀 경우, 위의 점수 저장 후 다음 줄로..
    int ret2 = solve(x + 1) + score[1][x];//아래 스티커를 뗀 경우, 아래 점수 저장 후 다음 줄로..
 
    return MAX(ret1, ret2);
}

그러나 위의 문제는 현재 스티커를 뜯었을 경우, 변을 공유하고 있는 스티커는 뜯을 수가 없다..

즉, 현재 스티커를 뜯은 경우에 따라 다음 선택에 영향을 주는 것이다.

우선 함수 자체에 바뀐 스티커의 상태를 알려줄 변수를 추가 후 상태에 따라 다른 스티커를 뜯게한다.

+그리고 현재 상태에서 둘다 뜯지 않은 경우를 추가한다. (이 경우 다음에서 위/아래 둘다 뜯을수가 있다.)

코드로 보면,

int solve(int x, int state)//현재 선택할 수 있는 스티커를를 알려줄 state변수 추가
{
    if (x >= n) return 0;
    int ret;
 
    switch (state)
    {
    case 0://위의 스티커를 뜯을 수 있다.
        ret = solve(x + 1, 1) + score[0][x];//위에를 뜯었으니 다음은 아래를 뜯을 수 있다고 알려준다.
    break;
    case 1://아래 스티커를 뜯을 수 있다.
        ret = solve(x + 1, 0) + score[1][x];//아래를 뜯었으니 다음은 위를 뜯을 수 있다고 알려준다.
    break;
    case 2://둘다 뜯을 수 있는 경우, 이전에 아무것도 뜯지 않은 경우이다.
        ret = solve(x + 1, 1) + score[0][x];
        ret = MAX(ret, solve(x + 1, 0) + score[1][x]);
    break;
    }
 
    ret = MAX(ret, solve(x + 1, 2));//아무것도 뜯지 않은 경우. 점수를 더하지 않고 2전달.
 
    return ret;
}

2. DP를 적용합니다.

이렇게 하면 완전탐색으로 구할 수 있습니다.. 하지만 여기까지만 하면 시간초과가 발생.. DP를 적용해야 합니다.

여기까지 했다면, DP를 적용하는건 쉽습니다. x까지 구한 최댓값을 state에 따라 값을 저장하면 됩니다.

아래 음영과같이 해주면 됩니다.

 
int DT[3][100001];
int solve(int x, int state)//현재 선택할 수 있는 스티커를를 알려줄 state변수 추가
{
    if (x >= n) return 0;
    if (DT[state][x] != -1) return DT[state][x];
 
    int ret;
    switch (state)
    {
    case 0://위의 스티커를 뜯을 수 있다.
        ret = solve(x + 1, 1) + score[0][x];//위에를 뜯었으니 다음은 아래를 뜯을 수 있다고 알려준다.
        break;
    case 1://아래 스티커를 뜯을 수 있다.
        ret = solve(x + 1, 0) + score[1][x];//아래를 뜯었으니 다음은 위를 뜯을 수 있다고 알려준다.
        break;
    case 2://둘다 뜯을 수 있는 경우, 이전에 아무것도 뜯지 않은 경우이다.
        ret = solve(x + 1, 1) + score[0][x];
        ret = MAX(ret, solve(x + 1, 0) + score[1][x]);
        break;
    }
 
    ret = MAX(ret, solve(x + 1, 2));//아무것도 뜯지 않은 경우. 점수를 더하지 않고 2전달.
 
    return DT[state][x] = ret;
}
 

전체 코드는 아래와 같습니다.

저는 단계별로 구현하는 과정을 설명하고 있는데요, 처음부터 DP를 이용해 bottom-up 방식을 이용하셔도 됩니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int n;
int score[2][100001];
int DT[3][100001];
 
int MAX(int a, int b)
{
    return (a > b) ? a : b;
}
 
int solve(int x, int state)
{
    if (x >= n) return 0;
    if (DT[state][x] != -1) return DT[state][x];
 
    int ret;
    switch (state)
    {
    case 0:
        ret = solve(x + 1, 1) + score[0][x];
        break;
    case 1:
        ret = solve(x + 1, 0) + score[1][x];
        break;
    case 2:
        ret = solve(x + 1, 1) + score[0][x];
        ret = MAX(ret, solve(x + 1, 0) + score[1][x]);
        break;
    }
 
    ret = MAX(ret, solve(x + 1, 2));
 
    return DT[state][x] = ret;
}
 
 
int main(int argc, char **argv)
{
    int testcase;
    scanf("%d", &testcase);
 
    for (int tc = 0; tc < testcase; tc++)
    {
        scanf("%d", &n);
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &score[i][j]);
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < 3; j++)
                DT[j][i] = -1;
        
        int max = 0;
        for (int i = 0; i<= 2; i++)
            max = MAX(max, solve(0, 2));
        printf("%d\n", max);
        
    }
    return 0;
}