[백준] 1053번 - 가장 긴 증가하는 부분 수열

1) 문제

수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다.

예시

A = {10, 20, 10, 30, 20, 50}

 

가능한 증가 부분 수열 중 하나

10 → 20 → 30 → 50

 

따라서 정답은 4이다.

여기서 중요한 점은 "연속된 수열이 아니라 부분 수열"이라는 점이다.

즉 중간 값을 건너뛰어도 된다.

---

2) 처음 접근 (실패했던 아이디어)

처음에는 다음과 같이 2차원 DP를 생각할 수도 있다.

dp[i][j] = i까지 고려했을 때 j를 선택한 경우

 

하지만 이렇게 설계하면

• 상태 수가 불필요하게 많아지고
• 문제 해결에 필요하지 않은 정보까지 저장하게 된다.

LIS 문제에서는 사실 마지막 원소만 알면 충분하다.

그래서 1차원 DP로 해결하는 것이 정석적인 방법이다.

---

3) 핵심 아이디어

DP 배열을 다음과 같이 정의한다.

dp[i] = i번째 원소를 마지막으로 하는 가장 긴 증가 부분 수열의 길이

 

예를 들어 arr[i] = 30 이라면

... → 30

 

으로 끝나는 LIS 길이를 의미한다.

---

4) 점화식

i 이전의 원소들을 확인하면서 현재 값보다 작은 경우만 이어붙일 수 있다.

조건

arr[j] < arr[i]

점화식

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

초기값

dp[i] = 1

자기 자신만 선택하는 경우이다.

---

5) Python 구현

 

import sys
input = sys.stdin.readline

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

dp = [1] * n

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

print(max(dp))

 

---

6) 시간 복잡도

이 풀이의 시간복잡도는 O(N^2)이다.

문제 조건 N ≤ 1000 이므로 충분히 통과 가능하다.