백준 9465 스티커

9365번 스티커

문제 설명

• 상근이의 여동생인 상냥이가 해당 스티커를 사 왔는데, 스티커 한 장을 떼면 그 스티커와 변을 공유하는 스티커는 사용할 수 없다고 한다.
• 각 스티커마다 점수를 매겼는데 여기서 점수의 합이 최대가 되도록 스티커를 떼는 경우를 구하고자 한다.
• 가장 높은 점수를 구해라!!

문제 접근

• 합을 구하는데 조건이 있으니까 DP다!!
• 변을 접하지 않는 애들 중에서 가장 큰 값과 더하면 되겠구나
• 변을 접하지 않는 애들 : 한 칸 앞 대각선, 두 칸 앞에 있는 스티커 위 아래 두 장.
  • 세 칸 앞 이상은 고려하지 않아도 되는 이유 : 세 칸 앞의 스티커와 바로 다음으로 현재 스티커를 고르면 사이의 두 칸에서는 아무 스티커도 고르지 않는다는 가정인데, 이렇게 되면 세 칸 앞의 스티커 하나와 그 대각선에 있는 두 칸 앞 스티커 하나와 내 현재 스티커를 고르는 경우가 무조건 더 크게 되므로 고려하지 않아도 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int T, n;

    cin>>T;
    while (T--)
    {
        int dp[2][100001];
        int input[2][100001];
        int ret = 0;

        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 100001; j++)
            {
                dp[i][j] = 0;
                input[i][j] = 0;
            }
        }
        cin>>n;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin>>input[i][j];
            }
        }
        dp[0][0] = input[0][0];
        dp[1][0] = input[1][0];
        // 핵심 로직 반복문
        for (int j = 1; j < n; j++)
        {
            for (int i = 0; i < 2; i++)
            {
                if (i == 0)
                {
                    if (j > 1)
                        dp[i][j] = max(dp[i + 1][j - 1], max(dp[i + 1][j - 2], dp[i][j - 2])) + input[i][j];
                    else
                        dp[i][j] = dp[i + 1][j - 1] + input[i][j];
                }
                else
                {
                    if (j > 1)
                        dp[i][j] = max(dp[i - 1][j - 1], max(dp[i - 1][j - 2], dp[i][j - 2])) + input[i][j];
                    else
                        dp[i][j] = dp[i - 1][j - 1] + input[i][j];
                }
            }
        }
        ret = max(dp[0][n - 1], dp[1][n - 1]);
        cout<<ret<<endl;
    }
    return (0);
}

느낀 점

• DP는 감이 잘 안 잡혀서 항상 어려웠던 분류였는데 이제 조금 감이 잡힌다는 느낌이 들었다.
• DP는 큰 문제를 작은 문제로 쪼개서 푸는 게 가장 큰 포인트라고 배웠었는데, 내 생각에는 이전의 계산 결과를 이용해서 최적의 결과를 만드는 게 중요한 포인트 같다.
• 배열을 활용한 메모이제이션으로 연산 횟수를 줄이고 이 과정을 하려면 큰 문제를 작은 문제로 쪼개서 생각해야 하는 것 같다.