99클럽 코테 스터디 28일차 TIL: 부분 수열 DP 업그레이드 버전

오늘의 문제 | 11055. 가장 큰 증가하는 부분 수열

대충 읽고 지난번 코드와 비슷하겠다는 생각이 들었다. 단순히 가장 긴 증가하는 부분 수열인 줄 알았으나 가장 큰 증가하는 부분 수열임을 보고 약간은 다른 부분이 있겠구나 했다.

1. 기존에 DP에 저장하던 것은 현재까지 가장 큰 값.
2. (1) 기본적으로 선형 순회 (2) 자기 아래에 존재하는 부분 수열들 중 본인을 포함하여 만들어지는 최댓값 수열을 찾아다님.

n=int(input())
l=[*map(int,input().split())]

dp=l[:] # 기존에는 길이였기에 1로 시작했으나 이번에는 0으로 시작함.
# 앞에서 픽한 친구보다 내가 크면, 그 친구에서 본인을 추가한 값만큼으로 최댓값을 갱신함.

for i in range(1,n):
    for j in range(i):
        if l[j]<l[i]:
            dp[i]=max(dp[i],dp[j]+l[i])
print(max(dp))

드디어 해당 문제의 유형을 이해했다. 본인보다 앞에서 본인보다 작은 값이 나오면, 그 친구가 갖고 있던 최댓값에 본인을 더하는 방식인 것이다.

 

어제랑 코드 자체에서 차이는 거의 없다시피하지만 코드를 오늘은 완벽하게 이해하고 짰다는 데서 의의가 있다. 확실히 비슷한 유형을 풀어서 그런지 이해가 빨리 됐다.

오늘의 회고

솔직히 문제보고 돌려막기 하는건가 싶었는데, 실제로 풀어보니 같은 코드임에도 꽤나 도움이 되었다. 아무래도 처음 푸는 분들의 경우 첫째날을 제대로 풀기 어려워서 검색할 것들 대비하여 응용할 문제를 냈나 싶었다.

 

DP 기피증이 있었기에 처음에 약간 두려웠으나 DP 리스트가 어떤 역할 하는지만 명확하게 알면 그리 어렵지 않은듯하다.