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

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

https://www.acmicpc.net/problem/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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

---

문제 유형

 

다이나믹 프로그래밍

 

풀이 방법 도출

주어진 수열에서 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이를 구하는 문제입니다.

1. dp[i]를 i번째 원소를 마지막 원소로 하는 LIS의 최대 길이라고 정의합니다.
2. 각 인덱스 i에 대해 0 ~ i-1까지를 순회하면서, a[i] > a[j]이면, a[i]는 a[j] 뒤에 붙여서 증가 수열을 만들 수 있으므로 dp[i] = max(dp[i], dp[j] + 1) 로 갱신합니다.
   
   
3. 마지막에는 dp 배열의 최댓값을 출력하면 됩니다.

 

시간 복잡도

• 이중 반복문 : O(N^2)

 

---

 

코드

 

import sys

# 수열의 길이 입력
n = int(sys.stdin.readline())

# 수열 A 입력
a = list(map(int, sys.stdin.readline().split()))

# dp[i]는 i번째 원소를 마지막으로 하는 LIS의 최대 길이
dp = [1] * n  # dp 초기화는 모두 자기 자신만 포함된 길이 1의 LIS

# 모든 쌍에 대해 확인
for i in range(1, n):
    for j in range(i):
        # a[i]가 a[j]보다 크다면 증가 수열 조건 만족
        if a[i] > a[j]:
            # 기존 dp[i]와 dp[j] + 1 중 더 큰 값으로 갱신
            dp[i] = max(dp[i], dp[j] + 1)

# 가장 긴 증가 부분 수열의 길이는 dp 배열의 최댓값
print(max(dp))