백준 C# - 1149 +) 풀이

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

DP알아보러 가기

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

---

점화식 구하기

01 일단 작성해보자

예제 1번을 가지고 한 번 적어본 후에 관계성을 구해보았다. N = 1, N = 2, N = 3 차근차근 최솟값을 구하면서 다음 N을 구하면 되는 것을 밑에 오른쪽표에서 확인할 수 있다.

---

02 점화식 구하기

위의 관계성을 통해 아래와 같이 점화식을 구할 수 있다.

---

코드 전문

using System;
namespace baek2
{

   class Program 
   {
       public static void Main()
       {
            int n = int.Parse(Console.ReadLine());
            int[,] arr = new int[1001 ,4];
            int[,] dp = new int[1001, 4];
            for (int i = 0; i<n; i++)
            {
                string[] token = Console.ReadLine().Split();
                for (int j = 0; j<3;j++)
                {
                    arr[i, j] = int.Parse(token[j]);
                }
            }
            dp[0,0] = arr[0,0];
            dp[0,1] = arr[0,1];
            dp[0,2] = arr[0,2];
            for(int i = 1; i<=n;i++)
            {
                dp[i, 0] = Math.Min(dp[i - 1, 1], dp[i - 1, 2]) + arr[i,0];
                dp[i, 1] = Math.Min(dp[i - 1, 0], dp[i - 1, 2]) + arr[i,1];
                dp[i, 2] = Math.Min(dp[i - 1, 0], dp[i - 1, 1]) + arr[i,2];
            }

            Console.Write(Math.Min(Math.Min(dp[n - 1, 0], dp[n - 1, 1]),Math.Min(dp[n - 1, 0], dp[n-1,2]))); 
       }
   }
}