[백준 14231번] 박스 포장 (C++)

문제링크 :  https://www.acmicpc.net/problem/14231

14231번: 박스 포장

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int arr[5001];
int dp[5001];

int main() 
{
   ios_base::sync_with_stdio(false); 
   cin.tie(0);

   int N;
   cin >> N;
   for(int i=1; i<=N; i++)
   {
      cin >> arr[i];
   }
   
   int result = 0;

   for(int i=1; i<=N; i++)
   {
      dp[i]=1; //초기값
      for(int j=1; j<i; j++)
      {
         if (arr[j] < arr[i]) //앞에 있는 박스가 뒤에 있는 박스보다 작아지면
         {
            dp[i] = max(dp[i], dp[j]+1);
         }
      }
      result = max(result, dp[i]); //과대 포장 최대치 저장
   } 

   cout << result;

   return 0;
}

dp 문제이다.

각 값마다 시작값은 1이기에 dp[i]를 1로 초기화하고 시작한다.

앞에 있는 박스가 뒤에 있는 박스보다 작아지면 현재 dp와 그전 dp + 1을 비교하여 큰 값을 넣고, 이렇게 구한 값중 최대치를 출력한다.