[백준] 알고리즘 1965번 - 상자넣기 문제

문제

www.acmicpc.net/problem/1965

1965번: 상자넣기

소스코드

#include <bits/stdc++.h>
using namespace std;
int arr[1001];
int dp[1001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n,ans=0;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i]>arr[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
				ans = max(dp[i], ans);
			}
		}
	}
	cout << ans + 1;
}
 

풀이

DP에는 여러가지 유형이 있는데, 이 유형은 LIS 유형의 문제입니다.

LIS에 대한 기본지식만 있으면 쉽게 해결가능한 문제입니다.