[알고리즘 문제] 백준9465 - 스티커

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

9465번: 스티커

어느정도 dp적으로 생각하는데 좀 익숙해지기 시작했습니다. 그리고 하나씩 예를 들면서 풀다보면 규칙을 발견하게 되고 이를 코드로 옮기면 되는 것 같습니다.

 

문제는 2행 n열 크기의 스티커에서 1x1크기의 스티커를 하나 제거하면 상하좌우의 인접한 스티커를 사용할 수 없습니다. 각각의 스티커에는 점수가 부여되어 있는데, 조건을 만족하면서 스티커를 제거할 때 최대점수를 구하면 되는 문제입니다.

 

문제를 풀때 2차원 배열 dp[][]를 사용했는데 dp[][]에 저장되는 값은 해당 스티커를 포함했을 때의 최대점수 입니다. 어쩃든 문제가 최대 점수를 구하는 문제 이기 때문에 이전에 구했던 최대점수를 사용하여 나중에 구하는 최대점수를 계산합니다.

 

규칙은 문제 조건에서 하나의 스티커를 선택하면 상하좌우의 스티커는 사용할 수 없다고 하였습니다. 그렇다면 상하좌우에 위치하지 않은 스티커의 최대값과 현재 스티커를 더한 값을 dp[i][j]에 넣어줍니다. 이를 풀어 설명하면 dp[i][j]에는 당연히 dp[i][j]를 선택한 경우의 최대값이기 때문에 dp[i][j]값을 더해주고, 추가적으로 상하좌우에 위치하지 않은, 내가 접근할 수 있는 위치의 스티커도 같이 더해줍니다. 당연히 해당 위치에는 해당 스티커를 선택했을때의 최대 점수가 적혀 있겠죠 ?

 

근데 상하좌우에서 오른쪽 방향을 신경쓸 필요가 없습니다. 왜냐하면..반복문에서 진행방향이 왼->우 이고, 오른쪽 방향을 미래의 값인데 그 값을 우리가 알 수 없기 때문이죠. 

 

그리고 문제 풀 때 중요한 점은 dp[i][j]위치에서 상하좌우로만 움직일 수 있다고 하였기 때문에 1행의 스티커는 왼쪽 아래, 2행의 스티커는 왼쪽위의 스티커에만 접근할 수 있습니다.

 

아무튼 현재의 값을 "접근할 수 있는 스티커의 점수(최대점수) + 현재 내 스티커 점수"를 현재 내스티커 점수에 넣으면서 값을 구하면 되는데, 문제는 "접근할 수 있는 스티커 중에서 최대점수를 가진 스티커를 어떻게 아느냐?" 이 부분은 topMax, bottomMax를 사용하여 dp[i][j]를 수정할 때 마다 topMax, bottomMax에 기존 값과 dp[i][j]의 최대값을 넣어주었습니다. 

 

마지막으로 dp배열을 int형으로 선언했는데, n의 범위가 10만이여서 혹시나 오버플로우가 되지 않을까 먼저 int형으로 제출했는데 통과가 되었습니다. 배열의 숫자가 생각보다 크지 않았네요.

 

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{

    int T;
    cin >> T;

    int dp[2][100001] = {0};

    while (T--)
    {
        int n;
        cin >> n;

        for (int i = 1; i <= n; i++) // 위쪽
        {
            cin >> dp[0][i];
        }
        for (int i = 1; i <= n; i++) // 아래쪽
        {
            cin >> dp[1][i];
        }

        int topMax = dp[0][1];
        int bottomMax = dp[1][1];

        for (int i = 2; i <= n; i++)
        {
            dp[0][i] = bottomMax + dp[0][i]; // 위쪽
            dp[1][i] = topMax + dp[1][i];    // 아래쪽

            topMax = max(topMax, dp[0][i]);
            bottomMax = max(bottomMax, dp[1][i]);
        }

        cout << max(dp[0][n], dp[1][n]) << "\n";
    }
    return 0;
}