[BOJ/C++] 상자넣기(1965번)

1. 개요

https://www.acmicpc.net/problem/1965

1965번: 상자넣기

1-1. 설명

정육면체 모양 상자가 일렬로 늘어서있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있다. 상자의 크기가 주어질 때, 한번에 넣을 수 있는 최대 상자 개수를 출력하는 프로그램을 작성한다.

1-2. 제한 사항

 - 파일의 첫번째 줄은 상자의 개수 n을 나타내며, n은 1 이상 1,000 이하

 - 둘째 줄에는 각 상자 크기가 순서대로 주어지며, 상자의 크기는 1,000을 넘지 않는 자연수

---

2. 구현

2-1. 풀이

DP의 Bottom-up 방식으로 문제를 풀었다. 0에서 i번째 상자까지 담을 수 있는 최대 상자 개수를 구하는 점화식을 생각해내면 된다. 

2-2. 코드

#include <iostream>
#include <algorithm>
using namespace std;

constexpr size_t MAX_NUM = 1001;
int input[MAX_NUM];
int dp[MAX_NUM];

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

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) cin >> input[i];
    fill(dp, dp + N + 1, 1);
    int result = 1;
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            if (input[j] < input[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        result = max(dp[i], result);
    }
    cout << result;
    return 0;
}