백준11053 - 가장 긴 증가하는 부분 수열 (DP) Python

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

해당 문제는 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제다.

인덱스 순서대로 가장 긴 수열을 구해나가면 결국 가장 긴 수열이 무엇인지 파악할 수 있으므로, 

다이나믹 프로그래밍(DP)으로 풀이가 가능하다.

 

먼저 각 인덱스 별로 가장 긴 수열의 길이를 저장해야 하므로 수열의 크기에 맞게 리스트를 만든다.

이때, 리스트에서 각 원소가 갖는 기본값(최솟값)은 1인데, 

수열에서의 각 인덱스들은, 자기 자신만을 갖는 길이 1의 수열을 만들 수 있기 때문이다.

 N, arr = int(data[0]), list(map(int, data[1].split())) 
 dp = [1 for _ in range(N)]

 

 

사실 처음 보는 문제 유형이다 보니, 문제가 어떤 흐름이며 점화식은 어떤 식으로 수립해야 하는지 몰라 직접 표로 그렸다.

인덱스	0	1	2	3	4	5
정수	10	20	10	30	20	50
최대 구성 수열	[10]	[10,20]	[10]	[10,20,30]	[10,20]	[10,20,30,50]
최대 수열 길이	1	2	1	3	1	4

 

표로 그리면 다음과 같은 그림이 그려진다.

이때 중요한 것이 있다면, 

뒷 순서의 정수가 앞 순서의 정수보다 크다면, 

인덱스 1의 최대 수열은 인덱스 0의 최대 수열인 [10]을 포함, (인덱스 1 수열 길이 = 인덱스 0 수열 길이 + 1)

인덱스 3의 최대 수열은, 인덱스 1의 최대 수열인 [10,20]을 포함, (인덱스 3 수열 길이 = 인덱스 1 수열 길이 + 1)

인덱스 4의 최대 수열은, 인덱스 0또는 2의 최대 수열인 [10]을 포함, (인덱스 4 수열 길이 = 인덱스 0 || 2 수열 길이 + 1)

인덱스 5의 최대 수열은, 인덱스 3의 [10,20,30,50]을 포함하고 있다는 것. (인덱스 5 수열 길이 = 인덱스 3 수열 길이 + 1)

이라는 결과가 만들어진다는 것.

 

따라서 아래와 같은 반복문을 통해 이를 구현할 수 있다.

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

dp[0]은 무조건 다른 수열에 담기는 역할이며, i > j 를 만족해야 하므로 1 ~ N -1 까지 첫 반복문의 범위를 잡는다.

또 인덱스 i의 입장에서는 i 이하의 인덱스인 정수밖에 포함할 수밖에 없기에 비교를 위한 반복은 0 ~ i -1 까지 두 번째 반복문의 범위.

그리고 위와 바찬가지로 각 정수값을 비교하여 dp에 값을 추가하는데,

이때 dp[i]는 이미 'arr[i]를 포함한 가장 긴 증가하는 부분 수열의 길이'를 나타내므로, dp[j] + 1와 비교하여 큰 값으로 값을 수정해나간다.

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  N, arr = int(data[0]), list(map(int, data[1].split()))
  
  dp = [1 for _ in range(N)]
  for i in range(1, N) :
    for j in range(i) :
      if arr[i] > arr[j] :
        dp[i] = max(dp[i], dp[j] + 1)
    
  print(max(dp))
  
solution(input_data)