[백준 11053] 가장 긴 증가하는 부분 수열 [Python]

백준 11053 - 문제

백준 11053 - 입/출력

---

풀이

LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다.

즉, 가장 긴 비연속 부분 수열의 길이를 알아내면 된다.

 

그렇다면, LIS는 어떻게 만들어 지는가?

기본적으로 위에서 언급했 듯 이전 요소보다 큰 요소가 나오면 된다. 문제의 입력에서 알 수 있듯 항상 증가만 하는 요소로 주어지지 않는다.

아래 그림을 보자.

입력받은 배열 A와, 배열에 대한 LIS 길이를 기록할 dp배열이 있다.

그 아래에는 단순히 이전 요소보다 큰 요소가 나오는 경우만 기록한 Increasing Subsequence이다.

 

첫 번째 경우 10 - 20 - 30 - 50으로 정답과 일치하는 길이가 나왔다!

하지만 다음과 같은 경우를 생각해보자.

1 - 2 - 8 - 1 - 2 - 3 - 4 - 5 - 6 
처음부터 이전 요소보다 큰 요소가 나오는 경우만 기록하면, 1 - 2 - 8으로 길이는 3이 나올 것이다.

하지만 정답은 1 - 2 - 3 - 4 - 5 - 6 으로 길이는 6이다.

 

때문에 아래와 같은 조건을 만족하는 경우 기록을 갱신해 주는 과정을 거쳐야 한다.

단, 모든 요소는 자기 자신이 LIS가 될 수 있으니 최초 길이를 1로 설정해주자.

• 1 ~ N 번 요소 모두 자기 자신보다 앞에있는 요소를 대상으로 탐색을 한다.

• 앞선 요소가(A[j])가 자신 보다(A[i]) 작고, A[j]까지 만들 수 있는 LIS길이가 A[I]까지 탐색한 LIS길이와 같다면, 
  A[i]는 A[j] 다음으로 이어지는 Increasing Subsequence이기에 A[i]에 대한 길이를 A[j] 보다 1만큼 증가시켜 준다.

위의 과정이 끝나면 모든 요소에 대해 비연속적인 LIS 길이가 dp 배열에 기록됬을 것이다. 최장 길이를 출력해주자.

---

소스코드

소스코드 보기

---

출처

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