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

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _14002_boj boj = new _14002_boj();
 
            boj.boj_14002();
 
        }
    }
        internal class _14002_boj
    {
        public void boj_14002()
        {
            int n = int.Parse(Console.ReadLine());
 
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 
            int[] dp = new int[n];
            dp[0] = 1;
 
            for (int i = 1; i < n; i++)
            {
                int max = 0;
                for (int j = i - 1; j >= 0; j--)
                    if (arr[j] < arr[i] && max < dp[j])
                        max = dp[j];
                dp[i] = 1 + max;
            }
            int Max = dp.Max();
            Console.WriteLine(Max);
 
            List<int> arr2 = new List<int>();
 
            for (int i = n - 1; i >= 0; i--)
            {
                if (dp[i] == Max)
                {
                    arr2.Add(arr[i]);
                    Max--;
                }
            }
            arr2.Reverse();
            foreach (var _ in arr2)
                Console.Write(_ + " ");
        }
    }
}
 

어떻게 하면 부분 수열을 출력할 수 있을지 한참을 고민하다 도저히 좋은 방법이 떠오르지 않아 인터넷에 검색을 해 보왔다.

알고보니 그냥 배열의 밴 마지막 부분부터 다시 훑으며 가장 큰 번호의 원소를 넣고 번호를 1 줄이는 방법을 사용하면 매우 간단하게 답을 얻을 수 있었다....