11055

날짜 : 2022. 12. 27

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
dp = [0] * n

for i in range(n): dp[i] = num[i]

for i in range(1, n):
    s = 0
    for j in range(i):
        if num[j] < num[i]:  # 증가하는 부분수열인 경우
            dp[i] = max(dp[i], dp[j] + num[i])

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

 

 

풀이

- 백준 11722 (https://yhah.tistory.com/246) 와 거의 같은 문제다.

- 앞의 숫자들을 비교하면서 증가하는 부분수열을 만들 수 있는 경우 기존 dp값과 해당 값을 넣었을 때의 dp값을 서로 비교하면서 갱신해 나간다.

- 다만 모두 같은 값이 나오거나 본인 값 1개만으로 output이 나올 수 있기 때문에 각 dp값에는 본인 인덱스의 값들을 초기화한다.

 

 

알게된 점

- 

 

 

참고 사이트

- 테스트케이스 : https://joey09.tistory.com/108

[테스트케이스 추가] 백준 11055번: 가장 큰 증가 부분 수열 python, 파이썬