백준 11053번: 가장 긴 증가하는 부분 수열 (파이썬)

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

풀이

 

이 문제는 Longest Increasing Subsequence(LIS) 문제로, 대표적인 DP 문제 중 하나다. 유명한 문제 답게 백준에도 여러 시리즈로 있는데, 문제 번호가 높아질 때마다 빠른 시간복잡도로 해결할 것을 요구한다. 이 문제에서는 가장 느리고 이해하기 쉬운 방법으로 해결하였다.

dp 리스트는 입력 받은 수열의 동일한 인덱스를 마지막으로 하는 LIS의 길이를 저장한다. 예를 들어 {10, 20, 10, 30, 20, 50}에서 3번째 인덱스인 30을 보자. 30을 마지막으로 하는 LIS를 구하기 위해서는 수열에서 30 이전에 30보다 작은 수를 확인하면 된다. 30보다 작은 수들을 마지막으로 하는 LIS에 30을 추가하면 30을 마지막으로 하는 LIS가 된다. 이 아이디어로 계산해 보면 30을 마지막으로 하는 LIS는 {10, 20, 10, 30}으로 길이가 3이다. 마찬가지로 다른 인덱스에 대해서도 생각해 보면, dp = {1, 2, 1, 3, 2, 4}가 된다.

아래 코드는 위의 설명을 그대로 구현한 것이다. 모든 인덱스에 대해 dp 리스트를 1로 초기화하고, 해당 인덱스 이전의 수열의 모든 값을 탐색하며 LIS의 길이를 업데이트한다. 그리고 마지막으로 dp 리스트의 최댓값을 구하면 문제를 해결할 수 있다.

 

소스 코드

n = int(input())

seq = list(map(int, input().split()))

dp = []
for i in range(n):
  dp.append(1)
  for j in range(i):
    if seq[i] > seq[j]:
      dp[i] = dp[j] + 1 if dp[j] + 1 > dp[i] else dp[i]

print(max(dp))