BOJ : 1965 상자넣기

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

DP(다이나믹 프로그래밍)으로 해결가능하다.

이런 문제를 최장 증가 수열 (LIS, Longest Increasing Subsequence) 이라고도 한다.

웬만한 크기가 작은 LIS문제는 아래의 코드로 다 해결이 가능하다

• LIS O(N^2)의 시간복잡도의 코드

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

#include <stdio.h>
int a[1001],lis[1001];
int main(){
    int N, max=0;
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        scanf("%d",&a[i]);
    
    for(int i=0; i<N; i++){
        lis[i] = 1;
        for(int j=0; j<i; j++){
            if(a[j] < a[i] && lis[i] < lis[j]+1){
                lis[i]=lis[j]+1;
            }
        }
        if(max < lis[i]) max=lis[i];
    }
    printf("%d\n",max);
}