[BOJ/백준] 11053번 가장 긴 증가하는 부분 수열 (LIS) (Python 파이썬)

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

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

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4

 

---

위와 같은 문제 유형을 LIS, Longest Increasing Subsequence로 불리는 유형입니다.
LIS 문제를 푸는 방법은 (1) 완전 탐색 (2) 동적 계획법 (3) 이진 탐색 등이 있는데, 시간 복잡도를 따져본다면 당연히 이진 탐색이 가장 효율적인 해답임을 알 수 있습니다. 하지만 해당 문제는 N (1 ≤ N ≤ 1,000)으로 주어지기 때문에 Dynamic Programing 기법으로도 충분히 풀이가 가능하므로, 해당 포스팅에서는 DP 기법을 사용한 풀이를 진행하고 이진 탐색 풀이는 다음으로 넘기겠습니다.

풀이

1. 우선 부분 수열의 길이를 저장한 리스트, dp를 선언합니다.
2. 이중 for문을 통해서 입력으로 받은 전체 수열을 순차적으로 비교합니다.
3. 이때, 오른쪽의 값이 더 크다면 증가하는 수열이 될 가능성이 있습니다.
4. dp[i]와 dp[j] + 1을 비교하여 최댓값을 저장합니다.
   이로써 dp에는 각 인덱스에 "해당 인덱스를 끝으로 하는 부분 수열의 최대 길이"가 담기게 됩니다.
5. dp에서 가장 큰 값을 출력합니다.

from sys import stdin
input = stdin.readline
N = int(input())
num = list(map(int, input().split()))
dp = [1]*N

for i in range(N):
    for j in range(i):
        if num[i] > num[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))