[백준] 11055번: 가장 큰 증가하는 부분 수열 - python

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

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

 

처음 작성한 아이디어

for문으로 돌면서 자기 자신보다 작으면 sum에 저장을 계속 해나가면서 high로 증가하는지 여부 체크

그 후 전 dp와 sum을 비교해 최대값을 저장하는 방식으로  구현을 했었다.

 

n = int(input())

arr = list(map(int, input().split()))
dp = [0] * (n+1)

dp[0] = arr[0] #첫번째 가장 큰값


for i in range(1, n):
    sum = 0
    high = 0
    for j in range(i+1):
        if arr[i] >= arr[j] and high < arr[j]:
            high = arr[j]
            sum+=arr[j]
    dp[i] = max(dp[i-1], sum)
    
print(max(dp))

 

5
10 90 20 80 100
[10, 100, 100, 110, 200]

 

그러나 문제는 다음과 같이 발생하였다.  high에 값을  저장해나가면서 진행하니 10 -> 90(high) 0 -> 100 이런식으로 진행하여 최종으로 200을 도출함으로 완전히 틀린 값이 나오게 되었었다.

 

DP에 값을 잘못저장한 결과였다. 다시 든 생각은 자신보다 작은 값을 DP에 저장할 것이 아니고 증가하는 수열의 합을 저장하고 그 중 최대값을 찾아내는 방식이 맞는 것 같아서 다시 코드를 작성하였다.

 

n = int(input())

arr = list(map(int, input().split()))
arr.append(0)
dp = [1] * (n+1) #증가하는 수열의 합을 저장한다.

dp[0] = arr[0] #첫번째 가장 큰값 

for i in range(1, n): # 2 1 2 => 2 1 3
    for j in range(i+1):
        if arr[i] > arr[j]: #만약 i번째가 더 크다면
            dp[i] = max(dp[i], dp[j] + arr[i]) #증가하는 수열의 j번째에서 i와 비교
        else:
            dp[i] = max(arr[i], dp[i])
        
print(max(dp))

 

성공.. DP는 어렵다