[C#] 백준 9465번 문제풀이

문제번호: 9465

문제명: 스티커

문제링크: https://www.acmicpc.net/problem/9465

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

오늘은 스티커 떼어내기 DP 문제를 풀었습니다. 각 스티커에는 점수가 있고, 스티커를 떼어내면 위,아래,양옆 스티커가 홰손됩니다. 스티커가 붙은 데이터가 주어질 때, 스티커를 떼어내어 얻을 수 있는 최대 점수를 알아내야합니다.

우선 경우의 수는 다음과 같습니다.

1. 1번째 줄 뒤 스티커를 떼어낸다.
2. 2번째 줄 뒤 스티커를 떼어낸다.
3. 건너뛴다.

이를 통해 점화식을 만들어볼 수 있습니다.
위쪽 스티커와 아래쪽 스티커를 떼어가면서 점수를 누적시켜줍니다.

dp[0, k] = Math.Max(dp[1, k - 1], dp[1, k - 2]) + sticker[0, k];
dp[1, k] = Math.Max(dp[0, k - 1], dp[0, k - 2]) + sticker[1, k];

이후 dp의 끝줄에서 첫번째와 두번째줄 점수 중 더 큰것이 얻을 수 있는 최대점수가 됩니다.
다음은 정답코드입니다.

static void Main()
{
    using StreamReader sr = new StreamReader(Console.OpenStandardInput());
    using StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int T = int.Parse(sr.ReadLine()!);
    for (int i = 0; i < T; i++)
    {
        int n = int.Parse(sr.ReadLine()!);
        int[,] dp = new int[2, n];
        int[,] sticker = new int[2, n];


        for (int j = 0; j < 2; j++)
        {
            int[] stickers = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            for (int k = 0; k < n; k++)
            {
                sticker[j, k] = stickers[k];
            }
        }

        dp[0, 0] = sticker[0, 0];
        dp[1, 0] = sticker[1, 0];

        if (n > 1)
        {
            dp[0, 1] = dp[1, 0] + sticker[0, 1];
            dp[1, 1] = dp[0, 0] + sticker[1, 1];

            for (int k = 2; k < n; k++)
            {
                dp[0, k] = Math.Max(dp[1, k - 1], dp[1, k - 2]) + sticker[0, k];
                dp[1, k] = Math.Max(dp[0, k - 1], dp[0, k - 2]) + sticker[1, k];
            }
        }


        sw.WriteLine(Math.Max(dp[0, n - 1], dp[1, n - 1]));
    }
}