[C#]백준 11053번: 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

---

• 문제

---

• 문제풀이

반복문을 사용해서 큰 수가 나올때마다 카운팅해주어 MAX값을 찾아내었다.

 

---

• 코드 1

using System;

class MainClass
{
    public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        int[] output = new int[n];
        int max = 1;

        for (int i = 0; i < n; i++)
        {
            output[i] = 1;
            for (int j = 0; j < i; j++)
            {
                if (input[j] < input[i] && output[i] < output[j] + 1)
                {
                    output[i] = output[j] + 1;
                }
            }
            max = Math.Max(max, output[i]);
        }

        Console.WriteLine(max);
    }
}

 

---

• 후기

다이나믹 프로그래밍은 항상 접근하기 어렵다. 많이 노력해야겠다.