[알고리즘] DP유형 - 백준 11053번 파이썬 (가장 긴 증가하는 부분 수열)

 

 

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

 

예제 입력

6 10 20 10 30 20 50

 

예제 출력

4

 

풀이

'가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)' 문제는  DP유형 중 잘 알려진 유형이다.

이 문제를 해결하는 방법에는 여러가지가 있겠지만, N의 범위가 최대 1000이므로 1차원 다이나믹 프로그래밍으로 O(N^2)의 시간복잡도로 문제를 해결할 수 있다.

 

입력받은 수열을 array라고 하고 DP테이블을 dp라는 리스트로 구현한다고 했을 때,

dp[i]를 array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이를 저장한다고 하자.

 

먼저, dp테이블의 모든 원소를 1로 초기화 한다. 모든 i에 대해 dp[i]는 최소 1이기 때문이다.

dp테이블의 인덱스 0인 요소부터 하나씩 써보자.

 

문제에 나온 예제에 따라 array = [10, 20, 10, 30, 20, 50]

초기값 dp = [1, 1, 1, 1, 1, 1]

 

• dp[0] = 1

  dp = [1, 1, 1, 1, 1, 1]

 

• dp[1] : array[0] < array[1] -> True => 1 + 1 = 2

  dp = [1, 2, 1, 1, 1, 1]
  

 

• dp[2] : array[0] = array[2] -> False => 1(초기값 그대로)
              array[1] = array[2] -> False => 1(초기값 그대로)
             >> 모든 j에 대하여  array[j] < array[2]가 False이므로 초기값(1) 유지

  dp = [1, 2, 1, 1, 1, 1]

 

• dp[3] = array[0] < array[3] -> True => 1(=dp[0]) + 1 = 2

               dp = [1, 2, 1, 2, 1, 1]
               array[1] < array[3] -> True => 2(=dp[1]을 의미) + 1 과 2(=현재 d[3]을 의미) 중 큰 값 = 3
               dp = [1, 2, 1, 3, 1 ,1]
               array[2] > array[3] -> True => 1(=d[2] 값을 의미) + 1과 3(= 현재 d[3]을 의미) 중 큰 값 = 3
               dp = [1, 2, 1 ,3 ,1 ,1]

 

즉, 특정 i번째 자리에서는 array배열의 1번째부터 i-1번째까지 모든 값들과 차례대로 비교해서 (1부터 i-1번째를 j 라고 하자)

array[j] < array[i] 일 때만 

dp[j]값 +1이 지금까지 저장한 dp[i] 값보다 크면 dp[i]값을 갱신하는 방법으로 풀 수 있다.

 

이를 점화식으로 표현하면 아래와 같다.

모든 0 <= j < i에 대하여 array[j] < array[i] 일 때만 dp[i] = max(dp[i], d[j] + 1) 

 

 

코드

import sys

n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

# 모든 i에 대해 dp[i]는 최소 1이므로 1로 초기화
dp = [1] * 1001


for i in range(n):
    # j < i 일때 arr[j] < arr[i] 이면 dp[i] = max(dp[i], dp[j] + 1)
    # arr[j] > arr[i]면 무시 (아무 것도 하지 않음)
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)


print(max(dp))