백준 11053 - 가장 긴 증가하는 부분 수열 (LIS)

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

11053번: 가장 긴 증가하는 부분 수열

동적 계획법을 사용하는 대표적인 알고리즘인 LIS 찾기 문제이다.

i번째 원소에 대한 LIS의 길이 dp[i]는 다음과 같이 구할 수 있다.

 

i번째 원소부터 다시 LIS를 시작 >> 1

i번째 원소가 기존 LIS에 포함 >> max(dp[j]) + 1    (1 <= j < i)

dp[i] = max(1, max(dp[j]) + 1)

 

위의 점화식에서 i가 기존의 어떤 LIS에도 포함되지 않을 경우

즉 arr[i]가 수열의 앞의 모든 원소보다 작을 경우 dp[i]는 1부터 다시 시작한다.

 

이렇게만 계산해 arr[n]을 결과값으로 반환한다면, 만약 arr[n]이 배열의 최소값일 경우

반환값이 1이 되는 불상사가 발생한다. 따라서 dp[i]와 별도로 i가 갱신될 때마다

현재까지 LIS 길이의 최대값을 다른 변수에 저장해야 한다.

 

배운 내용 :

계속해서 강조했지만 이미 계산된 앞의 결과를 어떻게 사용할지가 DP 문제 풀이의 관건이다.

이번 문제에서는 단순히 앞의 k개를 사용한 것이 아니라

처음부터 현재 위치까지 모든 경우를 고려했다.

 

따라서 현재 위치에서의 값을 계산하기 위해 어떤 원소들이 필요한 지를 잘 판단해야 한다.

 

LIS : 현재 위치까지 전부

계단 오르기 : 앞의 3개 원소