[C#] 백준 11722번 문제풀이

문제번호: 11722

문제명: 가장 긴 감소하는 부분 수열

문제링크: https://www.acmicpc.net/problem/11722

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

 

안녕하세요. 오늘도 다이내믹 프로그래밍 문제를 풀었습니다. 이번 문제는 예전에 풀었었던 '가장 긴 증가하는 부분 수열'과 유사한 문제입니다. 디피배열을 i, j 이진탐색으로 i와 j를 비교하여 더 작다면 mx와 j 중 더 큰 것을 mx로 교체합니다. j주기가 끝나면 mx값을 디피배열에 채워 넣습니다. 마지막에는 디피배열에서 가장 큰 값을 출력하여 가장 긴 감소하는 부분 수열의 길이를 알아낼 수 있습니다.

다음은 정답코드입니다.

 

public static void Main()
{
    StreamReader sr = new StreamReader(Console.OpenStandardInput());
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int N = int.Parse(sr.ReadLine());
    int[] A = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

    int[] dp = new int[N];

    for (int i = 0; i < N; i++)
    {
        int mx = 0;
        for (int j = 0; j < i; j++)
        {
            if (A[i] < A[j])
            {
                mx = Math.Max(mx, dp[j]);
            }
        }

        dp[i] = mx + 1;
    }

    sw.WriteLine(dp.ToList().Max());

    sr.Close();
    sw.Close();
}