[BOJ] [Python] 11055번 : 가장 큰 증가 부분 수열

[1, 100, 2, 50, 60, 3, 5, 6, 7, 8]를 예로 이해하고 해결해보자.

 

dp에는 자기 자신의 값이 초깃값으로 들어가 있다.

이제 0번째부터  9번째까지 하나씩 확인하며, dp를 늘려줄 것이다.

 

규칙은 아래와 같다.

 

n번째) 0번째부터 n-1번째까지 돌면서,

 

1. n번째 수보다 작은 값을 찾는다.

2. 작은 값들이 가진 dp중 최대의 dp를 n번째 dp에 더해준다.

 

 

예를 들어, 지금 4번째라고 한다면

50보다 작은 값은 1과 2이다.

1보다 2의 dp값이 더 크므로, 2의 dp값에 50을 더해준다.

더해진 값은 50의 dp값이 된다.

 

 

마지막에 dp 리스트의 최댓값을 출력하면, 가장 큰 증가 부분 수열의 합을 찾을 수 있다.

 

num = int(input())

li = list(map(int, input().split()))
dp = [0] * num

for now in range(num):

    tmp = 0
    dp[now] = li[now]

    for i in range(now):
        if li[i] < li[now] and tmp < dp[i]:
            tmp = dp[i]

    dp[now] += tmp

# print(dp)
print(max(dp))

 

 

 

 

처음에 수열이 중간부터 시작할 수 있다는 점을 간과하고 풀었다.

 

아래는 잘못된 코드이다.

 

num = int(input())

li = list(map(int, input().split()))
dp = [0] * num

dp[0] = li[0]

for now in range(num):

    tmp = 0

    for i in range(now):
        if li[i] < li[now] and tmp < dp[i]:
            tmp = dp[i]
            dp[now] = li[now] + dp[i]

print(max(dp))

 

dp[now] = li[now]를 안 해줬기 때문에,

맨 앞을 가지고 가지 않는 수열은, 존재할 수 없게 된다.