[백준 11053] 가장 긴 증가하는 부분 수열 (C#, C++) - soo:bak

문제 링크

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

설명

N개의 수로 이루어진 수열이 주어지는 상황에서 N (1 ≤ N ≤ 1,000)과 수열이 주어질 때, 가장 긴 증가하는 부분 수열(LIS)의 길이를 구하는 문제입니다.

각 원소는 1 이상 1,000 이하이고, 부분 수열은 원래 수열에서 일부 원소를 제거하여 만든 수열입니다.

접근법

모든 부분 수열을 확인하면 2^N이 되어 시간 초과가 발생합니다.

하지만 i번째 원소를 마지막으로 하는 LIS 길이는 이전 위치들의 LIS 길이에만 의존하므로 동적 프로그래밍을 사용합니다.

dp[i]를 i번째 원소를 마지막으로 하는 증가 부분 수열의 최대 길이로 정의합니다.

i번째 원소보다 작은 이전 원소들 중 LIS 길이가 가장 긴 것에 현재 원소를 추가하면 i번째 원소를 마지막으로 하는 LIS를 얻습니다.

예를 들어 수열 [10, 20, 10, 30, 20, 50]에서:

• 0번째 (10): 이전 원소 없음 → dp[0] = 1
• 1번째 (20): 10 < 20 → dp[1] = dp[0] + 1 = 2 (수열: 10, 20)
• 2번째 (10): 10과 20 모두 10 이상 → dp[2] = 1
• 3번째 (30): 10 < 30, 20 < 30 → 최대는 dp[1] + 1 = 3 (수열: 10, 20, 30)
• 4번째 (20): 10 < 20 → dp[4] = dp[0] + 1 = 2 또는 dp[2] + 1 = 2
• 5번째 (50): 모든 원소 < 50 → 최대는 dp[3] + 1 = 4 (수열: 10, 20, 30, 50)

모든 위치에서 이전 원소들을 확인하므로 시간 복잡도는 O(N²)이고, 최댓값이 답입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var a = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var dp = new int[n];
      Array.Fill(dp, 1);

      for (var i = 0; i < n; i++) {
        for (var j = 0; j < i; j++) {
          if (a[j] < a[i] && dp[i] < dp[j] + 1)
            dp[i] = dp[j] + 1;
        }
      }

      var ans = 0;
      for (var i = 0; i < n; i++)
        if (dp[i] > ans)
          ans = dp[i];

      Console.WriteLine(ans);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi a(n), dp(n, 1);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (a[j] < a[i])
        dp[i] = max(dp[i], dp[j] + 1);
    }
  }

  cout << *max_element(dp.begin(), dp.end()) << "\n";

  return 0;
}