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

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

문제

---

영선이는 과대 포장으로 유명한 남규 회사에서 아르바이트를 한다. 영선이는 여러 박스들을 여러겹으로 포장하는 업무를 맡았다. 박스를 포장할 때 규칙이 있는데, 일단 박스를 일렬로 주어진다. 그리고 앞에 있는 박스가 뒤에 있는 박스보다 작아야지만, 뒤에 있는 박스에 넣을 수 있다. 뒤에 있는 박스를 앞에 있는 박스에 넣을 순 없다.

박스의 크기가 앞에서부터 일렬로 주어졌을 때, 최대한 박스안에 박스를 넣어 과대 포장한 박스 개수를 구하시오.

 

입력

---

첫째 줄에는 박스의 개수 n이 주어진다.(1 ≤ n ≤ 5000)

다음 줄에는 박스의 크기 A_i가 앞에서부터 차례대로 주어진다.(1 ≤ A_i ≤ 100,000)

 

출력

---

최대한 박스안에 박스를 넣어 과대 포장을 할 때, 그 박스들의 개수를 구하시오.

 

문제 풀이

---

dp 문제.

앞에 있는 박스를 바로 뒤에 위치한 박스에만 넣을 수 있는 것이 아니다. 따라서 문제는 가장 긴 증가하는 부분 수열을 구하는 문제로 재정의된다.

각 박스의 크기에 대해 박스의 개수를 저장하는 dp 배열을 만든다. i 반복문을 돌리면서 각 박스 크기에 대해 j(0 ≤ j ≤ i-1)박스를 i번째 박스에 넣을 수 있는지(=j번째 박스가 i번째 박스보다 작은지)를 확인한다. 만약 넣을 수 있다면 포장할 수 있는 박스의 개수는 j번째 박스의 개수+1가 된다. j번째 박스의 개수가 가장 큰 것을 선택해 해당 값에 +1 하여 dp[i]에 저장한다.

모든 탐색을 끝내고 나면 전체 박스 중 가장 많이 포장할 수 있는 박스의 개수를 출력해주면 된다.

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* arr = new int[N];
	int* dp = new int[N];
	int answer = 1;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	dp[0] = 1;
	for (int i = 1; i < N; i++)
	{
		int maxLength = 0;
		for (int j = 0; j < i; j++)
		{
			if (arr[i] > arr[j] && dp[j] > maxLength)
			{
				maxLength = dp[j];
			}
		}
		dp[i] = maxLength + 1;
		answer = max(answer, dp[i]);
	}
	cout << answer << "\n";
	return 0;
}