[백준] 11053번 (python 파이썬)

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

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

 

이 문제는 LIS 라는 유명한 문제라고 한다.

처음 이 문제를 읽고 DP가 왜 필요하지? 생각했다.

맨 처음수를 temp에 넣고 다음 수와 비교하면서 큰수가 나오면 바꿔치기 하고 count하면 될 줄 알았다.

즉, 1, 3, 5, 4, 6라는 수열이 있다면

1을 temp에 넣고 3과 비교, temp에 3을 넣고 count를 1증가...하는식으로 생각했었다.

하지만 수열이 1, 100, 2, 3, 4 라면 LIS가 [1, 2, 3, 4]가 아닌, [1, 100]이 되어버리므로 생각을 버렸다.

 

이런 유형을 처음봐서 그런가 답을 보고도 잘 이해가 되지 않았다.

메모이제이션을 위한 정의조차 어려웠다.

 

수열(arr) [6, 2, 5, 1, 7]이 있다.

캐시로 사용할 배열(length)은 다음과 같이 정의한다.

length[n] : arr[0]부터 arr[n]까지(단, 마지막 값으로 arr[n]는 무조건 포함)의 LIS의 길이

 

length[0] = [6]의 길이인 1

length[1] = [2]의 길이인 1

length[2] = [2, 5]의 길이인 2

length[3] = [1]의 길이인 1

length[4] = [2, 5, 7]의 길이인 3

 

length = [1, 1, 2, 1, 3]  

 

length[n+1]의 값으로는 (arr[n+1]이 제일 작은 값일 때) 1 또는 (arr[n+1]이 arr[1~n]보다 클 때) length[1 ~ n] + 1이다.

예를 들어 arr[5]가 6라고 한다면, arr[1]인 2, arr[2]인 5, arr[3]인 1 보다 크므로 만들어 질 수 있는 증가하는 수열은

[2, 6]와 [2, 5, 6]와 [1, 6]이 만들어 질 수 있다. 그리고 이들 중 LIS는 [2, 5, 6]이므로 length[5] = 2가 된다.

 

이렇듯 length[n]는 length[n+1], length[n+2], length[n+3], ... 을 계산할때 재사용된다.

따라서 length배열은 캐시로 사용되어야 한다.

 

n = int(input())
values = list(map(int,input().split()))
length = [1 for _ in range(n)]

for i in range(n):
  for j in range(i):
    if values[i] > values[j]:
      length[i] = max(length[i], length[j] + 1)
print(max(length))