백준 C# - 14002 +) 풀이

문제를 읽어보면

입력이 1000이니까 1000*1000 = 1000000(백만)이므로 O(N²) 알고리즘으로도 이 문제는 충분히 통과 가능하다.

 

알고리즘

01 문제 분석

가장 긴 증가하는 부분수열 거의 동일하지만 한 가지 추가된 조건이 있다.

단순히 수열의 길이만 구하는 것이 아니라 그 실제 수열의 내용도 출력해야한다.

 

02 경로 복원(Path Reconstruction)

그 값을 만들기 위해 어떤 선택을 했는지를 저장해서 실제해를 구성할 수 있게 하는 방법이다.

 

경로 복원에 대한 정보 저장 - prev 배열

prev[i] = dp[i]를 만들기 위해 선택된 이전 인덱스, 즉 dp[i]가 dp[j]+1로 갱신되었으면 prev[i] = j를 저장하는 것이다.

10 20 10 30 20 50

i	list[i]	dp[i]	prev[i]
0	10	1	-1
1	20	2	0
2	10	1	-1
3	30	3	1
4	20	2	0
5	50	4	3

index 5 → 3 → 1 → 0 → -1
value 50 → 30 → 20 → 10

 

 

알고리즘 흐름

1. dp[] 을 채운다. 

각 위치까지의 가장 긴 증가 수열의 길이 계산

2. 가장 큰 dp[i]를 찾는다.

dp[i]가 가장 큰 위치 = LIS 마지막 원소

3. prev[]배열을 거꾸로 따라가며 수열을 복원한다.

Stack 사용해 앞에서부터 출력

---

코드 전문

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Solution
{
    static void Main()
    {
        long n = long.Parse(Console.ReadLine());
        int[] list = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        long[] dp = new long[n + 1];
        int[] prev = new int[n];
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++)
        {
            dp[i] = 1;
            prev[i] = -1;
            for (int j = 0; j < i; j++)
            {
                if (list[i] > list[j] && dp[i] < dp[j] + 1)
                {
                    prev[i] = j;
                    dp[i] = dp[j] + 1;
                }
            }
        }
        int max = 0;
        for (int i = 1; i < n; i++)
        {
            if (dp[i] > dp[max])
                max = i;
        }

        Stack<int> sequence = new Stack<int>();
        while (max != -1)
        {
            sequence.Push(list[max]);
            max = prev[max];
        }
        sb.Append(list.Max());
        Console.WriteLine(dp.Max()); 
        Console.WriteLine(string.Join(" ", sequence));
    }
}