C# 백준 20162 간식 파티 (동적계획법)

20162번: 간식 파티

IDEA

이 문제는 아주 오래전 시도했다가 틀린 문제다.

시간 보니 야간 연등 중에 했던 것 같다.

입출력만 겨우겨우 하던 당시에는 너무 어렵다고 생각해서 취침 시간을 12분 남겨놓고 포기했던 모양이다.

 

문제를 간단히 정리하면 이렇다.

1. 서울이는 N일 동안 이어지는 간식 파티에서 간식을 골라 먹는다.

2. 서울이는 이전에 먹었던 간식보다 더 평점이 높은 간식만 먹는다.

3. 간식 파티가 끝날 때까지 서울이가 먹은 간식의 평점 총합의 최고치는?

오늘이 i일이고 오늘 주어지는 간식의 평점을 snack[ i ], 오늘까지 평점 합 최고치를 dp[ i ]라고 하자. 서울이가 오늘의 간식을 먹는다고 해보자. 그렇다면 dp[ i ]는 이전의 dp[ i - k ] ( k는 1 이상 i 이하) 에 snack[ i ]를 더한 값이다. 서울이가 오늘의 간식을 먹으려면 평점이 snack[ i ] 보다 낮은 간식만을 먹었어야 한다. 그렇다면 dp[ i ]는 다음과 같이 정리할 수 있다.

 

dp[ i ] = dp[ i - k ] + snack[ i ]

( 단, snack[ i ] > snack[ i - k ] 이고 k의 범위는 0 ＜ k ≤ i )

 

그럼 매일 간식을 받을 때마다 dp[ 0 ] 부터 dp[ i - 1 ] 까지의 값에 snack[ i ]를 더한 값 중 가장 큰 값을 dp[ i ] 로 남겨두면 된다.

 

 

CODE

using System;
class Program
{
    static int N, max;
    static int[] snack, dp;
    static void Main()
    {
        N = int.Parse(Console.ReadLine());
        snack = new int[N]; dp = new int[N]; max = 0;
        for (int i = 0; i < N; i++)
            snack[i] = int.Parse(Console.ReadLine());
        for (int i = 0; i < N; i++)
        {
            dp[i] = snack[i];
            // dp[i]의 초기 값은 snack[i]다.
            // 이전의 어떤 간식도 고르지 않고
            // 오늘의 간식을 처음으로 먹은 경우다.
            
            for(int j = 0; j < i; j++)
                if (snack[i] > snack[j] && dp[i] < dp[j] + snack[i])
                    dp[i] = dp[j] + snack[i];
                // 오늘의 간식이 평점이 이전 간식보다 높아야한다.
                // dp[i]가 dp[j]에 오늘 평점을 더한 것보다 크면
                // dp[i]를 경신한다.
                
            max = dp[i] > max ? dp[i] : max;
            // 최대값 경신
        }
        Console.WriteLine(max);
    }
}