백준 [1965] 상자넣기

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

1965번: 상자넣기

 

LIS(Longest Increasing Subsequence, 최장 증가 수열)와 DP를 동시에 이용하는 문제

(LIS를 구하는 방법 중 하나가 DP라고 한다.)

 

- LIS란?

원소가 n개인 배열이 주어졌을 때, 이 배열의 원소를 뽑아 만든 부분 수열 중, 각 원소가 이전 원소보다 크며, 그 길이가 최대인 부분 수열을 의미한다.

ex) {6,2,5,1,7,4,8,3} 의 LIS -> {2,5,7,8}

DP문제로 자주 나오는 유형이며, O(N^2)와 O(NlogN)의 시간복잡도를 갖는 두가지의 알고리즘이 존재한다고 한다.

이 문제에서 사용하는 방법이 O(N^2)의 알고리즘이며, O(NlogN)은 이분탐색을 활용해야한다.(자세한 것은 모름)

 

해결 방법)

dp[i] = 자신보다 이전에 있는 원소들 중 작은 원소들의 개수 + 1(자기자신 포함)

-> 먼저, 자기 자신보다 작은 수들을 for문을 통해 찾고, 이 작은 수들의 dp값을 하나씩 보며 이 중 최댓값을 찾아준 후 최댓값 + 1을 해준다.

ans를 사용해서 max값을 업데이트해줘야하는 이유

-> 맨 마지막 값이 가장 큰 값은 아니므로 최댓값이 어디에 속해 있을지 모르므로 i가 바뀔때마다 dp[i]와 ans를 비교해서 큰 값으로 저장해줘야 한다.

box[j]<box[i] && dp[i]<dp[j]+1 //핵심 LIS 방식

-> 두개의 조건을 모두 만족해야하는 이유

이 문제는 자기 자신보다 작은 수의 개수만 찾는 문제가 아니다. 오름차순으로 정렬되는게 아니고, 각 인덱스에서의 최대 상자개수를 찾아야 하는 문제이기 때문