[알고리즘/동적 계획법] 11055 번 : 가장 큰 증가하는 부분 수열 - python

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

11055번: 가장 큰 증가하는 부분 수열

 

---

• 문제
• 소요시간: 15분 30초

---

• 설계하기(접근방법) 

1. n과 arr를 입력받는다

2. 알고리즘 해석

 

1) 현재 dp값을 저장하는 법

i = 0일 때, 현재 값 저장

i > 1일 때, 이전의 dp와 비교한다.

 

증가하는 수열이기 위해서는 현재 arr[i](ex:60)의 값이 이전 arr(ex:1, 2, 50)값보다 커야 한다.

 

-> 현재 arr값보다 작은 arr값중 max(dp)(ex : 53 = 50 + 2 + 1) 값을 가진 값을 가져오고, 그 값에 자신의 arr[i](ex: 60)를 더해준다

 

result : 113

 

3. max(dp)를 출력한다

 

 

 

---

• 코드(출력)

n = int(input())

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

dp = [0 for _ in range(n)]

for i in range(n):
    if i == 0:
        dp[i] = arr[i]
    else:
        big = 0
        for j in range(i):
            if arr[i] > arr[j]:  # 현재보다 작은 수를 가진 원소들 中
                if dp[j] > big:
                    big = dp[j]
        dp[i] = big + arr[i]

print(max(dp))

---

• 얻어갈 부분

1. 1 번째, 2번째 원소를 하나씩 체크해보며 어떤 식을 세워야 문제를 풀 수 있을지 고민했다. 이전 dp값이 크더라도, 현재 원소의 값보다 큰pd값이면 증가하는 수열이 아니라는 아이디어에서 출발했다.