[백준] 9465번: 스티커 [C#]

 

스티커에 가치를 메긴 후, 가장 가치가 높은 스티커의 집합의 가치를 구하려 한다.

하지만, 서로 변을 공유하는 스티커는 동시에 뗄 수 없다.

 

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
using System.Runtime.Intrinsics.Arm;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
 
            for (int i =0; i < n; i++)
            {
                int m = int.Parse(Console.ReadLine());
                int[,] arr = new int[2, m];
 
                int[,] dp = new int[2, m];
 
                for (int a = 0; a < 2; a++)
                {
                    int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                    for (int b = 0; b < m; b++)
 
                        arr[a, b] = input[b];
                }
 
                dp[0, 0] = arr[0, 0];
                dp[1, 0] = arr[1, 0];
                if (m == 1)
                {
                    Console.WriteLine(Math.Max(dp[0, 0], dp[1, 0]));
                    continue;
                }
 
                dp[0, 1] = dp[1, 0] + arr[0, 1];
                dp[1, 1] = dp[0, 0] + arr[1, 1];
                if (m == 2)
                {
                    Console.WriteLine(Math.Max(dp[0, 1], dp[1, 1]));
                    continue;
                }
 
                for (int k = 2; k < m; k++)
                {
                    dp[0, k] = Math.Max(dp[1, k - 2], dp[1, k - 1]) + arr[0, k];
                    dp[1, k] = Math.Max(dp[0, k - 2], dp[0, k - 1]) + arr[1, k];
 
                }
                Console.WriteLine(Math.Max(dp[0,m-1], dp[1,m-1]));
            }
        }
    }
}
 

 

지금까진 보통 입력이 1차원의 배열로만 주어졌지만, 이번에는 2차원의 배열로 주어졌다.

따라서 dp도 2차원으로 만들어서 사용해주었다.

우선 dp의 0번지, 1번지에 각각의 값을 넣어 주었다

이를 통해서 m이 1 혹은 2로 주어졌을 때 해당 열의 최대값(1, 2차원 중)을 반환하면 된다.

나는 이 예외처리를 continue로 해줘야 하는데, return으로 한번에 함수를 끝내버려서 문제가 되었었다.

 

원하는 값은 dp배열 안의 값이다(위의 그림은 arr 안의 값)

변을 공유하는 스티커는 사용이 불가능하므로 대각선으로 있는 값을 가져온다.

dp[0, i - 2]의 값도 가져올 수 있지만, dp[1, i -1]에 포함되어있을 수 있는 수이기 때문에 무시한다.

대각선 위/ 아래의 값들 중 큰 것을 가져와서 자신이 가지고 있는 값과 더한 후 dp에 저장한다.

이를 반복해서, 가장 큰 값을 리턴 해주면 된다