[C/C++ 백준 1965번] 상자 넣기 (Silver 2)

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

1965번: 상자넣기

백준 11055번 가장 큰 부분 증가 수열과 완전히 같은 문제이다. 다만 수열의 합이 아니라 크기를 구하는 문제인데, dp에 A[i](원소의 크기)를 더하는 대신 1을 더하는 것으로 해결된다.

---

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int N, A[1001]={}, dp[1001]={}, maxi, ans=-1;
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		scanf(" %d",&A[i]);
		maxi=-1;
		for(int j=0; j<i; j++){
			if(A[j]<A[i])
				maxi=max(maxi, dp[j]+1);
		}
		maxi=max(maxi, 1);
		dp[i]=maxi;
		ans=max(ans, dp[i]);
	}
	printf("%d",ans);
}

---