[백준/파이썬] 11053번: 가장 긴 증가하는 부분 수열

문제

https://www.acmicpc.net/problem/11053

풀이

최장 증가 부분 수열(LIS) 알고리즘을 사용하는 문제

LIS란?

Longest Increasing Subsequence의 약자이다.
LIS는 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘이다.
부분 수열이 연속적이거나 유일할 필요는 없다.

LIS는 DP나 이진 탐색을 활용하여 문제를 해결할 수 있습니다.
저는 DP를 활용하여 문제를 풀어봤습니다.

최장 길이를 저장할 배열을 선언

dp = [1] * n

여기서 왜 배열을 1로 초기화했냐면 최소의 길이가 1이기 때문입니다.
(최소한 자기 자신만으로도 증가 부분 수열의 길이가 1이기 때문)

이후 반복문을 통해 각 요소를 비교하여 길이를 업데이트해줍니다.

for i in range(1,n): # i번째 원소에 대해
    for j in range(n): # i보다 작은 j번째 원소들을 비교
        if arr[i] > arr[j]: # i번째 원소가 j번째 원소보다 크다면 증가 수열 가능
            dp[i] = max(dp[i], dp[j]+1) # LIS 길이 갱신

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
dp = [1] * n
for i in range(1,n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))