백준 C# - 11052 +) 풀이

 

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

DP알아보러 가기

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

---

풀이

점화식 찾기

01 손으로 적어보자

dp와 Pn과의 관계를 한 번 손으로 적어보면 아래와 같이 나오는 것을 확인할 수 있다.

 

02 점화식

위의 경우의수들 중 제일 큰 값을 골라서 dp[i]에 넣어주면 된다. 그러므로 점화식을 구해보면 아래와 같이 나온다.

---

코드 전문

using System;
namespace baek2
{
    class Program
    {
        static void Main()
        {
            int num = int.Parse(Console.ReadLine());
            string[] str = Console.ReadLine().Split();
            int[] dp = new int[num + 2];
            int[] p = new int[num + 2];
 
            for(int i = 1; i<=str.Length;i++)
            {
                p[i] = int.Parse(str[i-1]);
            }
            for(int i = 1; i <= num ;i++)
            {
                for(int j = 1; j<=i; j++)
                {
                    dp[i] = Math.Max(dp[i], dp[i - j] + p[j]);
                }
            }
            Console.Write(dp[num]);
        }
    }
}