[BOJ 11053] 가장 긴 증가하는 부분 수열

09 Mar 2026

Reading time ~3 minutes

문제 요약

수열 A가 주어질 때, 가장 긴 증가하는 부분 수열(LIS) 의 길이를 출력한다.

1 ≤ N ≤ 1,000

내가 받은 작은 힌트 (핵심 아이디어)

처음에는 dp[i]를 “i번째까지 봤을 때의 정답” 같은 식으로 잡으려고 했는데, 그렇게 두면 상태가 애매해져서 점화식이 깔끔하게 안 나온다.

대신 힌트는 이거였다:

dp[i]를 “i번째 원소를 반드시 마지막으로 사용하는 증가 부분 수열의 최대 길이”로 두면 된다.
그러면 arr[i] 앞에 올 수 있는 이전 원소들을 검사하게 된다.

이 관점으로 바꾸니까 점화식이 자연스럽게 나온다.

점화식

dp[i] = i에서 끝나는 LIS 길이
초기값: 모든 원소는 자기 자신만으로 길이 1의 증가 수열을 만들 수 있음 → dp[i] ≥ 1

이때, a[j] < a[i]인 모든 j(<i) 중에서 가장 긴 것을 이어붙이면 된다.

dp[i] = max(dp[j] + 1) (단, j < i이고 a[j] < a[i])
가능한 j가 없으면 dp[i] = 1

정답은 max(dp).

내 코드

n = int(input())

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

part = [1]

for i in range(1, n):
    temp_max = 1
    for j in range(i):
        if a[j] < a[i] and part[j] >= temp_max:
            temp_max = part[j] + 1
    part.append(temp_max)

print(max(part))

코드 개선 포인트 (가독성)

현재 코드도 정답이고 N=1000이라 O(N^2)로 충분히 통과한다.

다만 조건식 part[j] >= temp_max는 의미가 조금 헷갈릴 수 있어서, 아래처럼 “그냥 max로 갱신” 형태가 더 읽기 쉽다.

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

dp = [1] * n

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

print(max(dp))

이 버전에서 배울 수 있는 점

dp = [1] * n으로 초기화하면 append 없이도 인덱스로 업데이트 가능
dp[i] = max(dp[i], dp[j] + 1) 형태가 LIS의 전형적인 점화식을 그대로 드러냄
조건을 최소화해서 로직이 더 명확해진다

이번 문제로 배운 점

DP는 상태 정의가 핵심이고, LIS에서는 dp[i]를 “i에서 끝나는 최장 길이”로 정의하면 점화식이 깔끔해진다.
O(N^2)이 무조건 느린 게 아니라, N=1000 정도면 충분히 통과할 수 있다.
더 큰 N에서는 이진 탐색 기반 O(N log N) LIS가 필요하지만, 이 문제는 기본 DP로 충분하다.