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

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

 

해당 문제는 다이나믹 프로그래밍을 활용하여 풀이할 수 있는 문제다.

 

풀이과정은 다음과 같다.

먼저 가장 큰 부분 수열의 '합'을 구하는 것이므로

DP 테이블의 기본값은 입력값으로 초기화한다. (이는 자기 자신만 포함하는 경우이기도 하다.)

이후 두번째 반복문의 범위는 0 <= j < i 로 설정하는데,

현재 요소 arr[i]를 기준으로 이전 요소들을 비교하며 가장 긴 증가하는 부분 수열의 합을 갱신하기 위함이다.

(따라서 현재 요소 이전의 모든 요소들을 순회)

 

증가하는 부분 수열이므로 arr[i]가, arr[j]보다 크다는 조건을 만족하며, (arr[i] > arr[j])

현재 요소를 마지막으로 한 부분 수열의 합 dp[i]보다

현재 요소 값 + 이전 요소를 마지막으로 한 부분 수열 합(arr[i] + dp[j])의 값이 클 경우 (arr[i] + dp[j] > dp[i])

dp[i] 를 arr[i] + dp[j] 로 수정해준다.

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

def solution (data) :
  n = int(data[0])
  arr = list(map(int, data[1].split()))
  dp = [* arr]

  for i in range(n) :
    for j in range(i) :
      if arr[i] > arr[j] and arr[i] + dp[j] > dp[i] : 
        dp[i] = arr[i] + dp[j]

  print(max(dp))

solution(input_data)