[Baekjoon 11053 / Python / 실버2] 가장 긴 증가하는 부분 수열

문제

import sys

input = sys.stdin.readline

N = int(input())

numList = list(map(int, input().split()))

dp = [1] * N

for i in range(1, N):

    for j in range(i):

        if numList[i] > numList[j]:

            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

 

Longest Increasing Subsequence(LIS) 문제로, DP유형의 대표적인 문제 중 하나다.

처음엔 문제만 보고 뭐야 이게 진짜 실버2라고..? 란 생각과 함께 코드를 짜서 제출했지만 역시 실패했다.

 

나는 크게 두 가지를 간과했다.

1. 수열이 첫 번째 숫자부터 시작할 필요가 없다는 것

2. 더 큰 숫자가 나오더라도 그 숫자를 선택하지 않아도 된다는 것. 즉 넘어가고 다른 숫자를 선택해도 된다는 것.

 

1번에 대한 문제는 금방 고쳤지만, 2번은 굉장히 헷갈렸다. 그래서 정답코드를 참고해 공부하고 이해했다.

2번이 무슨 말이냐 하면, 10 20 100 30 40 50 이런 수열이 있다고 했을 때,

10 20 100 이렇게 끝나는 게 아닌, 100을 버리고 10 20 30 40 50 이렇게 가장 긴 수열을 만들 수 있는 숫자만 선택할 수 있다는 소리이다.

 

DP유형은 늘 그렇듯 이걸 어떻게 풀지..? 하고 머리를 싸매다가, 정답 코드를 보면 너무 짧아서 현타가 온다. 그냥 많이 풀어보는 게 답인 것 같다.