[Python] 백준 11055번: 가장 큰 증가 부분 수열 풀이

 

소스코드

n = int(input()) 
A = list(map(int, input().split())) 
dp = [x for x in A]
for i in range(n): 
    for j in range(i): 
        if A[i] > A[j]: 
            dp[i] = max(dp[i], dp[j] + A[i]) 
print(max(dp)) 

 

휴.. 풀이를 시작하기 전에 한 가지만 짚고 가자...

파이썬 문법을 제대로 알지 않고 무작정 알고리즘을 풀다 보니 오늘 그 쓴맛을 제대로 느꼈다....

dp = A 이렇게 하면 dp가 A를 참고하게 되어, 서로의 값에 영향을 주고 받는 다는 것을 몰랐던 나는 수십번 코드를 고쳤다 말았다 난리를 쳤다.........

휴!!! 그래도 새로운 거 알았으니 됐다.ㅎㅎㅎㅎ 앞으로 파이썬에서 list의 값을 그대로 복사(?) 초기화 하고 싶을 땐 그냥 귀찮아도 저렇게 쓰자...ㅋㅋㅋㅋ

 

 

11053이랑 거의 비슷하다고 해도 무방하다.

단지 이번에는 증가하는 수열의 길이와 상관이 없고, 합이 가장 크면 된다.

그래서 dp값을 수열과 동일하게 초기화 해주었다. 

그리고 이중 for문을 돌면서 자기의 dp값이 큰지, 아니면 자기보다 작은 j들 중 dp[j] + 자신의 수 가 더 큰지 비교해서 dp값을 갱신해 주면 된다.