백준 11053 - 가장 긴 증가하는 부분 수열 (Python3)

코드

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

# 자신 + 자신보다 작은 수의 개수를 담을 배열
# 증가하는 부분 수열이므로 자기 자신도 개수에 포함해야 하므로 1로 초기화
d = [1] * n

for i in range(1, n):
    for j in range(i):
        
        # j번째의 수가 i번째의 수보다 작다면
        if arr[j] < arr[i]:
            # 기존의 d[i]값과 d[j]+1의 값 중 더 큰 값으로 바꿈
            # d[j] + 1 => j까지의 수 + i 자신을 포함하여 + 1
            d[i] = max(d[i], d[j]+1)
            
print(max(d)) 

문제 해설

LIS (Longest Increasing Subsequence) 문제.

DP를 활용하여 풀 수 있는 매우 유명한 문제이다. DP 테이블에 자신보다 값이 작은 원소들의 개수를 저장하고 그 중 가장 큰 값을 구해주면 정답.

다양한 부분으로 응용될 수 있는 문제이므로 꾸준히 연습해야겠다.

---

LIS (Longest Increasing Subsequence)

배열에서 일부 원소를 골라내서 만든 부분 수열 중, 값이 계속 증가하는 부분 수열 을 증가 부분 수열이라고 하며 이 중 길이가 최대인 부분 수열을 LIS 즉, 최장 증가 부분 수열이라고 한다.

나무위키 참고