[알고리즘][백준] 11055번 가장 큰 증가하는 부분 수열 - 파이썬(python) 풀이

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

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

---

11053번 가장 긴 증가하는 부분 수열의 응용문제이다.

 

나는 바로 합계를 구하면 뭔가 꼬여서 답이 안나올줄 알고

 

일부러 dp를 2차원으로 숫자 [순서, 합]으로 2차원으로 만들었는데 꼭 그럴필요는 없다는 점...

import sys

n = int(sys.stdin.readline())

num = list(map(int, sys.stdin.readline().split()))

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

dp[0][1] = num[0]

m = 0

for i in range(n):

    for j in range(i):

        if num[i] > num[j]:

            dp[i][0] = max(dp[i][0], dp[j][0]+1)

            dp[i][1] = max(dp[i][1], dp[j][1] + num[i])

            m = max(m, dp[i][1])

print(m)

 

이렇게 하니 틀렸다고 뜨는데 num[j]가 num[i]보다 다 큰 경우가 발생할 수도 있기 때문에

 

else에 따로 num[i]의 값을 dp[i][1]에 넣어주어야 한다

import sys

n = int(sys.stdin.readline())

num = list(map(int, sys.stdin.readline().split()))
dp = [[1,0] for _ in range(n)]
dp[0][1] = num[0]
m = 0

for i in range(n):
    for j in range(i):
        if num[i] > num[j]:
            dp[i][0] = max(dp[i][0], dp[j][0]+1)
            dp[i][1] = max(dp[i][1], dp[j][1] + num[i])
        
        else:
            dp[i][1] = max(dp[i][1], num[i])
        
    m = max(m, dp[i][1])
            
print(m)

 

 

다른 분들은 dp를 2차원이 아니라 1차원으로 바로 합을 넣어 진행하셨다

 

메모리사용량은 동일하지만 시간은 확실히 더 빠르다

import sys

n = int(sys.stdin.readline())

num = list(map(int, sys.stdin.readline().split()))

dp = [0] * n
dp[0] = num[0]

for i in range(n):
    for j in range(i):
        if num[i] > num[j]:
            dp[i] = max(dp[i], dp[j]+num[i])
        else:
            dp[i] = max(dp[i], num[i])

print(max(dp))

11055_가장큰증가하는부분수열.py

0.00MB