챕터3-10. DP | 문제 풀이2 - (4) 백준 No.9465 : 스티커

스티커 문제

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

문제요약

2xn 모양으로 놓여진 스티커가 있는데 각각의 스티커는 점수를 가지고 있다.
한장을 뗄 때마다 변을 공유하는 상하좌우의 스티커는 찢어져서 사용할 수 없게된다.
이때 떼어낸 스티커 점수들의 합의 최대값을 출력하시오.

해결 방법

무조건 큰 수부터 뜯어내면 최대합을 만들 수 있을까? 정답은 X 이다. 아래의 2x3 모양의 스티커 예시를 보자.

99 100 99
1    99   1
가장 큰 수인 100을 뜯어내면 합은 100 + 1 + 1 = 102이고, 99를 뜯어낸다고 하면 99 + 99 + 99 = 297이다.
따라서 최대합을 만들기 위해 무조건 큰 수 부터 떼네는 것은 옳지 않다.

 

위의 이유로 뜯는 순서가 정해져 있지 않다고 생각하여 내가 직접 스티커를 떼는 순서를 정할 수 있다고 해보자.
그래서 왼쪽에서 오른쪽 방향으로 한 열씩 어떻게 스티커를 뜯을지 말지 결정해 줄 수 있다고 정하였다.
한 열에 대해서 가능한 경우는 3가지가 있다. O, O인 경우는 문제에서 제시한 조건에 위배되므로 제외한다.
[0]  [1]  [2]             X : 안뜯는 것, O: 뜯는 것
 X    O    X
 X    X    O

 

1. D[N]에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N] = "2xN의 스티커에서 떼네어 만들 수 있는 최대합"

- 맨 뒤에 오게될 케이스가 3가지 이기 때문에 배열을 2차원 배열로 확장시키게 되면 다음과 같이 될 수 있다.
   D[N][S] = "N번째에서 S액션을 취했을 경우 2xN의 스티커에서 떼네어 만들 수 있는 최대합"
   D[N][0] = "N번째에서 [0]액션을 취했을 경우 2xN의 스티커에서 떼네어 만들 수 있는 최대합"
   D[N][1] = "N번째에서 [1]액션을 취했을 경우 2xN의 스티커에서 떼네어 만들 수 있는 최대합"
   D[N][2] = "N번째에서 [2]액션을 취했을 경우 2xN의 스티커에서 떼네어 만들 수 있는 최대합"

 

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다.
   A : 2xN 카드 값이 들어있는 행렬

 

case 1) N번째 취할 액션이 [0]인 경우
- N-1번째에 올 수 있는 액션은 문제에서 제시한 조건에 따라 [0], [1], [2] 액션이고, 이때의 최대값은 다음과 같다.
- D[N][0] = max(D[N-1][0], D[N-1][1], D[N-1][2])

case 2) N번째 취할 액션이 [1]인 경우
- N-1번째에 올 수 있는 액션은 문제에서 제시한 조건에 따라 [0], [2] 액션이고, 이때의 최대값은 다음과 같다.
- D[N][1] = max(D[N-1][0], D[N-1][2]) + A[N][0]

 

case 3) N번째 취할 액션이 [2]인 경우
- N-1번째에 올 수 있는 액션은 문제에서 제시한 조건에 따라 [0], [1] 액션이고, 이때의 최대값은 다음과 같다.
- D[N][2] = max(D[N-1][0], D[N-1][1]) + A[N][1]

 

따라서 점화식은 D[N] = max(D[N][0], D[N][1], D[N][2]) 이다.

 

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

 

4. 코드구현

<Top-down 방식>

2차원 배열 방식으로 풀이하였으므로 더 쉬운 Bottom-up방식을 사용하자.

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100001][2];   // N번째라는 용어를 사용하여 알고리즘을 생각했으므로 index를 [1~100000][0~1] 를 사용할 수 있도록 함
int d[100001][3];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    for (int test_case = 0; test_case < T; test_case++)
    {
        int n;
        cin >> n;

        for(int i = 1; i <= n; i++)
            cin >> arr[i][0];

        for(int i = 1; i <= n; i++)
            cin >> arr[i][1];

        d[0][0] = d[0][1] = d[0][2] = 0;

        for (int i = 1; i <= n; i++)
        {
            d[i][0] = max(max(d[i-1][0], d[i-1][1]), d[i-1][2]);
            d[i][1] = max(d[i-1][0], d[i-1][2]) + arr[i][0];
            d[i][2] = max(d[i-1][0], d[i-1][1]) + arr[i][1];
        }
        
        cout << max(max(d[n][0], d[n][1]), d[n][2]) << "\n";
    }
}

 

(2) 시간복잡도
= for 문의 반복 횟수 

= O(N)