[백준 1965] 상자넣기 (C#, C++) - soo:bak

문제 링크

1965번 - 상자넣기

설명

상자들이 일렬로 놓여 있고, 앞 상자가 뒤 상자보다 작을 때만 앞 상자를 뒤 상자에 넣을 수 있는 상황에서, 한 번에 넣을 수 있는 최대 상자 개수를 구하는 문제입니다.

접근법

주어진 순서를 유지하면서 크기가 증가하는 상자들을 선택하는 것이므로, 가장 긴 증가 부분수열의 길이를 구하면 됩니다.

각 상자에 대해 해당 상자를 마지막으로 하는 증가 부분수열의 최대 길이를 구합니다. 현재 상자보다 앞에 있으면서 크기가 더 작은 상자들 중 가장 긴 부분수열에 1을 더하면 됩니다.

모든 상자에 대해 이 값을 구한 뒤 최댓값이 답이 됩니다.

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

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var parts = Console.ReadLine()!.Split();
    var a = new int[n];
    for (var i = 0; i < n; i++) a[i] = int.Parse(parts[i]);

    var dp = new int[n];
    var ans = 0;
    for (var i = 0; i < n; i++) {
      dp[i] = 1;
      for (var j = 0; j < i; j++) {
        if (a[j] < a[i] && dp[i] < dp[j] + 1)
          dp[i] = dp[j] + 1;
      }
      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);
  for (int i = 0; i < n; i++) cin >> a[i];

  vi dp(n, 1);
  int ans = 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;
    }
    ans = max(ans, dp[i]);
  }

  cout << ans << "\n";

  return 0;
}