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

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

1965번: 상자넣기

1. 주의할 점

- DP를 이용하여 푼다

 

2. 구현

- 현재 상자를 기준으로 왼쪽에 위치한 상자들만 생각한다

- 현재 상자보다 크기 작으면서, DP[] 값이(들어갈 수 있는 상자의 수) 가장 큰 수를 Maxi에 저장한다

- Maxi+1을 현재 상자번호에 해당하는 DP[] 배열에 할당한다. 할당 이후, Result의 값과 비교하여 최대값을 Result에 저장하도록 한다

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1000], arr[1000];

int main() {
	int num, result = 1;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> arr[i];
		dp[i] = 1;
	}
	for (int i = 1; i < num; i++) {
		int maxi = 0, idx = i;
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i]) {
				if (dp[j] > maxi)
					maxi = dp[j];
			}
		}
		dp[i] += maxi;
		result = max(result, dp[i]);
	}
	cout << result;
	return 0;
}