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

[문제]

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

크기가 다른 N개의 상자가 일렬로 늘어서 있다. 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있다. 이 때 한 번에 넣을 수 있는 상자 개수의 최대값을 구하는 문제이다.

[사용 알고리즘]

DP(다이나믹 프로그래밍)

[풀이 핵심]

• 이 문제는 가장 긴 증가하는 부분수열을 구하는 문제와 같다. 따라서 dp[x] = y 는 x번 상자까지 담을 수 있는 최대 상자 개수이다. 따라서 dp[N]까지 구해준다음 그 중 최대값이 정답이다.
• 먼저 dp[]배열은 상자 개수이므로 자기 자신이 무조건 포함되기 때문에 1로 초기화해준다. 그리고 현재 상자보다 앞에 있는 상자들 중 더 작으면서 그 상자안에 들어 갈 수 있는 상자의 최대값 +1을 한 값이 현재 상자에 넣을 수 있는 최대값보다 더 크면 그 값을 선택하는 식으로 dp[]배열을 갱신해가면 해결할 수 있다.

[코드]

//boj1965번_상자넣기_dp

#include<iostream>
#include<algorithm>

using namespace std;

int dp[1001];
int arr[1001];

int main() {
	int N;
	cin >> N;

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

	for (int i = 0; i < N; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
			}
		}
	}

	cout << *max_element(dp, dp + N + 1);

	return 0;
}