[백준] 11053번 가장 긴 증가하는 부분 수열 문제 풀이 (파이썬)

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

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

https://youtu.be/5Lu34WIx2Us

병사 배치하기 문제를 풀려다가 이 문제 먼저 푸는 게 나을 것 같아서 풀어보았다. 역시나 다이나믹 프로그래밍의 일종으로, 동빈님의 강의의 도움을 받았다.

가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)

D[i] = arr[i]를 마지막 원소로 가지는 부분 수열의 최대 길이라고 하자.
이 때 모든 0 <= j < i에 대하여(즉, i보다 앞에 있는 모든 원소 각각에 대하여)
if and only if arr[j] < arr[i] (앞의 원소가 더 작을 때 / 작은 경우에만)
D[i] = max(D[i], D[j] + 1) 테이블을 갱신해준다.

 

이해가 잘 안 가서 그림을 그려가면서 고민해보았는데, 다시 한 줄 한 줄 써보자면 다음과 같다.

 

arr의 모든 원소에 대하여, 각각의 원소를 "마지막 원소로 가지는" 증가하는 부분 수열의 최대 길이를 구해서 D에 업데이트해준다.

최종 정답은 그 D의 원소들 중 최댓값이 될 것이다.

 

이때 다이나믹 프로그래밍의 원리가 들어가는데,

다시 말하자면 이미 계산한 문제는 다시 계산하지 않을 수 있도록 하는 것이다.

 

arr의 원소 i에 대하여, 그 원소 앞의 모든 원소 j를 일일이 확인할 때

만약 arr[j] < arr[i]를 만족한다면, 즉 앞의 원소가 더 작다면

D[j] 즉 원소 j까지의 증가하는 부분 수열의 최대 길이에 1을 더해준 값이 잠정적으로 D[i]가 되는 것이다.

 

(같은 i의) 또 다른 j에 대하여 다시 arr[j] < arr[i]를 만족한다면

또 같은 방식으로 D[i]가 업데이트된다(기존의 D[i]와 D[j] + 1 중 더 큰 값으로 D[i]를 업데이트).

 

따라서 점화식은 다음과 같다.

 

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

n = int(input())
arr = list(map(int, input().split()))

# i가 0일 때 증가하는 최대 부분 수열의 길이는 1이기 때문에, 테이블을 우선 전부 1로 초기화해줌
d = [1] * n

for i in range(1, n): # 1부터 n - 1번 인덱스까지의 모든 i에 대하여
    for j in range(i): # i보다 작은 j 각각에 대해
        if arr[j] < arr[i]: # j의 원소가 i의 원소보다 작다면, 즉 부분적으로 증가한다면
            d[i] = max(d[i], d[j] + 1) # i에서의 최적의 해를 갱신해준다.

print(max(d)) # 가장 긴 증가하는 부분 수열의 길이 출력

병사 배치하기 문제는 가장 긴 감소하는 부분 수열로 응용해서 쉽게 풀 수 있다.