백준 C# - 9465 +) 풀이

DP를 이용해서 풀어야한다.

DP알아보러 가기

C# - 다이나믹 프로그래밍(DP)

---

점화식 구하기

처음에 점화식을 구하고 풀었는데 틀렸다. 1칸이 떨어진 경우와 2칸이 떨어진 경우 두가지 경우를 생각해야 했다. 예제를 예시로 보면 100에서 60사이에는 두 칸이 떨어져 있는 것을 확인할 수 있다.

점화식을 세워보자

1칸 , 2칸을 비교해서 큰 값을 dp에 넣으면 된다. 

점화식

---

코드 전문

using System;
namespace baek2
{

   class Program 
   {
        public static void Main()
        {
            int n = int.Parse(Console.ReadLine());

            while (n > 0)
            {
                int m = int.Parse(Console.ReadLine());
                string[] str1 = Console.ReadLine().Split();
                string[] str2 = Console.ReadLine().Split();
                long [,]arr = new long[3,m+5];
                long[,] dp = new long[3, m + 5];
                for(int i = 1; i<=str1.Length;i++)
                {
                    arr[0, i] = long.Parse(str1[i-1]);
                    arr[1, i] = long.Parse(str2[i-1]);
                }
                dp[0, 0] = 0;
                dp[1, 0] = 0;
                dp[0, 1] = arr[0, 1];
                dp[1, 1] = arr[1, 1];
                for (int i = 2; i <= m; i++)
                {
                    dp[0, i] = Math.Max(dp[1, i - 1], dp[1, i - 2]) + arr[0, i];
                    dp[1, i] = Math.Max(dp[0, i - 1], dp[0, i - 2]) + arr[1,i];
                }
                Console.WriteLine(Math.Max(dp[0,m],dp[1,m]));
                n--;
            }
        }
   }
}