백준 C# - 11053+) 풀이

문제풀이에 앞서 문제에서 제시된 시간복잡도를 분석해보자

제한 시간이 1초 → 일반적으로 연산량 1억 이내 가능하므로 입력에서 N의 크기가 1000이므로 O(N²)까지 허용된다.

---

이 문제를 풀기 앞서 LIS 개념을 알고 풀이를 진행하자

LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)란?

수열에서 일부 원소를 "순서를 유지한 채"골라서 값이 점점 증가하도록 만든 부분 수열 중 가장 긴 길이의 구하는 문제이다.

단 연손된 값일 필요는 없고, 앞에 선택된 값보다 커지기만 하면 된다.

 

예시

[10, 20, 10, 30, 20, 50]
→ 가장 긴 증가하는 부분 수열: 10 20 30 50 (길이 4)

 

LIS은 전형적인 DP 문제이다.

dp의 배열안에는 dp[i] : i번째 원소를 마지막으로 하는 LIS의 길이이다.

for (int i = 0; i < n; i++)
{
    dp[i] = 1; // dp[i] = i번째 원소를 마지막으로 하는 LIS의 길이
    for (int j = 0; j < i; j++)
    {
        if (A[j] < A[i]) //  앞에서 i보다 작은 수를 찾아서 수열 연결 가능 여부 판단
        {
            // dp[j] + 1 → A[j]까지의 수열 뒤에 A[i]를 붙인 경우
            dp[i] = Math.Max(dp[i], dp[j] + 1); // 최대값 갱신
        }
    }
}

위의 예시를 아래와 같은 표의 과정으로 확인할 수 있다.

i	A[i]	비교 대상 j (A[j])	비교 결과	dp[i] 갱신 과정	최종 dp[i]
0	10	없음	-	초기값 1	1
1	20	0 (10)	10 < 20 → ✅	max(1, dp[0]+1) = 2	2
2	10	0 (10)	10 < 10 → ❌	변경 없음
		1 (20)	20 < 10 → ❌	변경 없음	1
3	30	0 (10)	10 < 30 → ✅	max(1, dp[0]+1) = 2
		1 (20)	20 < 30 → ✅	max(2, dp[1]+1) = 3
		2 (10)	10 < 30 → ✅	max(3, dp[2]+1) = 2 → 유지	3
4	20	0 (10)	10 < 20 → ✅	max(1, dp[0]+1) = 2
		1 (20)	20 < 20 → ❌	변경 없음
		2 (10)	10 < 20 → ✅	max(2, dp[2]+1) = 2 → 유지
		3 (30)	30 < 20 → ❌	변경 없음	2
5	50	0 (10)	10 < 50 → ✅	max(1, dp[0]+1) = 2
		1 (20)	20 < 50 → ✅	max(2, dp[1]+1) = 3
		2 (10)	10 < 50 → ✅	max(3, dp[2]+1) = 2 → 유지
		3 (30)	30 < 50 → ✅	max(3, dp[3]+1) = 4
		4 (20)	20 < 50 → ✅	max(4, dp[4]+1) = 3 → 유지	4

---

코드 전문

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

class Solution
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int[] list = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
        long[] dp = new long[n + 1];
         for(int i = 0; i<n; i++)
            dp[i] = 1;
        for(int i = 0; i<n; i++)
        {
            for(int j = 0; j<i;j++)
            {
                if(list[j] < list[i])
                {
                    dp[i] = Math.Max(dp[i],dp[j] + 1);
                }
            }
        }

        Console.WriteLine(dp.Max());
    }
}