[백준 1965번] 상자넣기 (C++)

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

1965번: 상자넣기

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

int N, maxV;
int arr[1001];
int dp[1001];

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

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

    for(int i=0; i<N; i++)
    {
        dp[i]=1; //최소 개수 1
        for(int j=0; j<i; j++)
        {
            if(arr[i] > arr[j])
            {
                dp[i] = max(dp[i], dp[j]+1); //현재값과 그전값 + 1 비교
            }
            maxV = max(maxV, dp[i]); //가장 큰 값 저장
        }
    }
    cout << maxV;
}

 

나름 간단한 dp 문제이다.

먼저 최소 상자 개수는 1이기에 초기값은 1로 초기화해준다.

 

그리고 현재값과 현재값 기준 그 전 값들을 비교하여 탐색해준다.

만약 그전 값이 현재값보다 작다면, 현재값에 그전값 + 1과 현재값중 큰 값을 저장한다.

이를 반복하여 dp에 값을 저장해나가고 저장된 값들 중 가장 큰 값을 따로 저장하여 출력해주면 된다.