[백준] 11053번 가장 긴 증가하는 부분 수열 (by Python)

문제

내가 생각했던 것은 bottom-up 방식으로 for loop으로 0번째부터 i번째까지의 LIS(Longest Increasing Subsequence) 값을 저장해둔다는 것. 그렇지만 점화식을 세우는 것이 쉽지 않았는데, 이전 원소들의 정보를 충분히 활용할 수 없었기 때문이었다.

그래서 이코테 책을 보다가 알게 된 점화식은 내 기존 생각에 한 가지를 덧붙인 것이었는데, i번째 원소를 사용한다는 제약조건을 추가하는 것이다. 그렇게 마지막 원소까지 반복문을 수행한 후 max값을 찾으면 LIS의 길이를 구할 수 있다. 점화식을 생각할 때 정보가 충분하지 않은 것 같다면 정답으로 이어질 수 있으면서 고려할 범위를 좁혀줄 수 있는 제약조건을 주라는 것이 내가 이 문제에서 얻은 팁이다.

풀이

n = int(input())
a = list(map(int, input().split()))
dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))