[알고리즘 문제 풀기] 가장 긴 증가하는 부분 수열(11053)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (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];
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (a[i] > a[j]) dp[i] = Math.Max(dp[i], dp[j] + 1);
        }
        result = Math.Max(result,dp[i]);
    }
    sw.WriteLine(result);
}

3. 정리

• dp[i]를 i번째 숫자를 마지막 원소로 하는 가장 긴 증가 부분 수열의 길이로 설정한다.

• i보다 앞선 j를 탐색하며 a[i] > a[j]인 경우 dp[i] = Math.Max(dp[i], dp[j] + 1)로 갱신한다.

• 최종적으로 dp 배열의 최댓값을 구해 문제를 해결한다.