[백준/11055] 가장 큰 증가하는 부분 수열 (Python)

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

 

Difficulty : Silver 2

 

Status : Solved

 

Time : 00:13:25

 

---

 

문제 설명

 

 

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

 

첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

 

입력 예시

 

10
1 100 2 50 60 3 5 6 7 8

 

출력 예시

 

113

 

 

---

 

풀이

 

LIS 문제의 변형판. 조금은 색다르게 DFS와 DP의 조합으로 풀어 보았다. 이런 경우 최대 시간복잡도는 O(N^2)이 되므로 긴 수열에서는 사용할 수 없으나, 최대 N이 1000이므로 제한 시간 내에 모두 순회가 가능하다.

 

풀이 코드

N = int(input())
num_list = list(map(int, input().split()))
dp = [0]*N

def dfs(idx) :
  if dp[idx] > 0 :
    return dp[idx]
  
  dp[idx] = num_list[idx]
  for i in range(idx+1, N) :
    if num_list[i] > num_list[idx] :
      tmp = dfs(i)
      dp[idx] = max(dp[idx], num_list[idx] + tmp)

  return dp[idx]

for i in range(N) :
  dfs(i)
print(max(dp))

풀이 완료!