[알고리즘 문제 풀기] 조 짜기(2229)

1. 문제 풀이 아이디어

• dp[i]를 i번째 요소까지 고려했을 때의 최대 점수로 정의하고, 각 부분 배열의 최댓값과 최솟값을 이용하여 dp 값을 갱신하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());

    int[] s = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    int[] dp = new int[n + 1];
    for (int i = 0; i < n; i++)
    {
        int min = s[i];
        int max = s[i];
        for (int j = i; j >= 0; j--)
        {
            max = Math.Max(max, s[j]);
            min = Math.Min(min, s[j]);
            dp[i + 1] = Math.Max(dp[i + 1], dp[j] + max - min);
        }
    }
    sw.WriteLine(dp[n]);
}

3. 정리

• dp[i]는 i번째 요소까지 고려했을 때 얻을 수 있는 최대 점수를 저장한다.

• s[i]를 마지막 요소로 하는 부분 배열을 고려하며 max와 min 값을 갱신한다.

• j를 i부터 0까지 줄여가며 각 구간의 점수를 계산하고 dp[i+1] 값을 최대로 갱신한다.

• 최종적으로 dp[n]이 전체 배열에서 얻을 수 있는 최대 점수가 된다.