1. 문제

출처: 백준 11053번 가장 긴 증가하는 부분 수열

2. 풀이

이 문제의 경우에는 어떤 수열인지는 구할 필요가 없고, 길이만 즉 포함된 숫자의 개수만 구하면 된다.

구하려고 하는 부분 수열은 계속해서 증가하는 형태여야 하기 때문에, 살펴보려 하는 숫자보다 앞에 있는 숫자들 중 작은 것이 어떤 것들이 있는지 살피면 된다. 또한, 앞선 숫자들의 경우에도 그 숫자들보다 앞에 있는 숫자들은 작아야 한다.

Ex) (30,10,20,50) 같은 경우라면 30은 50보다 작긴 하지만, 부분 수열에 들어갈 수 없게 된다.

즉, 숫자들을 살필 때에 앞선 숫자가 지금 선택한 숫자보다 작다면, 앞선 숫자는 몇 개의 숫자를 부분 수열로 가지고 있는지 살핀 후 1개를 추가하면 되는 것이다. 다만, 다른 경우의 부분 수열 길이가 더 길 수도 있기 때문에 기존에 저장해오던 값과 새로 계산한 값 중 어떤 것이 더 큰 지 비교하는 과정이 필요하다.

3. 소스코드

n = int(input())
numbers = list(map(int,input().split()))

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

4. 그 외

부분 수열을 구하는 문제는 계속해서 유형을 달리해서 나왔던 것으로 기억한다. 그때마다 다르게 접근하는 것이 재밌게 느껴진다.