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

문제 링크

11722번 - 가장 긴 감소하는 부분 수열

설명

길이 N (1 ≤ N ≤ 1,000)의 정수 수열이 주어지는 상황에서, 가장 긴 감소하는 부분 수열의 길이를 구하는 문제입니다.

N이 최대 1,000이므로 O(N²) DP로 충분히 해결할 수 있습니다.

접근법

DP를 활용하여 각 위치에서 끝나는 가장 긴 감소 부분 수열의 길이를 계산합니다.

먼저 dp[i]를 i번째 원소를 마지막으로 하는 감소 부분 수열의 최대 길이로 정의합니다. 모든 dp 값은 최소 1로 초기화합니다.

다음으로 각 위치 i에 대해 앞에 있는 모든 원소 j를 확인합니다. a[j] > a[i]인 경우, 즉 감소하는 관계라면 dp[i]를 dp[j] + 1과 비교하여 더 큰 값으로 갱신합니다.

이후 모든 dp 값 중 최댓값이 가장 긴 감소하는 부분 수열의 길이가 됩니다.

시간 복잡도는 O(N²)입니다.

---

Code

C#

using System;

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

      var dp = new int[n];
      var best = 0;
      for (var i = 0; i < n; i++) {
        dp[i] = 1;
        for (var j = 0; j < i; j++) {
          if (arr[j] > arr[i] && dp[i] < dp[j] + 1)
            dp[i] = dp[j] + 1;
        }
        if (dp[i] > best)
          best = dp[i];
      }

      Console.WriteLine(best);
    }
  }
}

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);
  for (int i = 0; i < n; i++)
    cin >> a[i];

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

  cout << best << "\n";
  return 0;
}