99클럽 코테 스터디 27일차 TIL: 부분 수열 DP

오늘의 문제 | 11722. 가장 긴 감소하는 부분 수열

이 문제가 DP라고 하니 약간 머리가 아파졌다. 처음에는 그냥 뒤집에서 작은 거까지 내려오도록 하면 될 줄 알았으나, 생각보다 찾기 어렵지 않을까 하는 생각이 들었다. 하지만 N이 작기 때문에, 전부다 검사해도 되지 않을까 라는 생각도 든다.

1. 뭔가를 저장해놔야 접근이 가능할 것으로 보인다. 각 숫자를 시작점으로 생각했을 때의 길이를 생각하면 되는 것일까?
2. 가장 긴 증가하는 부분 수열을 반대로 해결하는 문제이다. 그렇다면 가장 긴 건 어떻게 구해야할까?

LIS (Longest Increasing Subsequence)

결국 순회화며 각 원소가 포함된 수열 중 가장 긴 것을 찾아내는 것으로부터 시작한다는 걸 검색으로 부터 알아냈다… 예전에 가장 긴 증가하는 부분 수열을 풀었었으나 이 코드를 봐도 쉽게 이해가 되지 않는다.

증가하는 가장 긴 수열을 알아냈다면 배열을 뒤집어서하면 감소하는 것도 확인할 수 있기에 문제는 바로 해결됐다.

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

dp=[1]*n

for i in range(1,n):
    for j in range(i):
        # 본인 앞까지의 원소들을 순회함.
        if l[i]>l[j]:
            # 만약 본인 앞에서 본인이 더 커지는 원소가 존재하면
            dp[i]=max(dp[i],dp[j]+1)
            # 기존 본인 숫자/본인보다 작은 수의 숫자+1 중 더 큰 값으로 갱신

print(max(dp))

이 코드에서 max 값이 뜻하는건, dp[j]+1은 해당 i를 선택해도 되는지에 대한 질문이다. 만약 이 값을 선택하는 것이 최대 길이에 도움이 된다면 취하는 느낌으로 보인다.

오늘의 회고

DP는 확실히 배우지 않고 문제를 푸는게 어렵다고 느껴지긴 한다. 어쩔 수 없이 찾아보긴 했지만 이런 아이디어를 떠올릴 수 있도록 확실하게 공부해놓는게 도움될거 같다.