문제 출처 : https://www.acmicpc.net/problem/11053
1. 문제 요약
- 수열 A[0..N-1]에서
- 인덱스 순서만 유지하며
- 값이 증가하는 부분 수열 중
- 가장 긴 것의 길이를 구한다.
연속일 필요는 없다.
2. DP 핵심 아이디어
DP 정의:
dp[i] = A[i]를 마지막으로 하는 증가 부분 수열(LIS)의 최대 길이
A[i] 혼자만 있어도 길이 1짜리 LIS가 되므로 기본값은 1.
점화식:
dp[i] = max(dp[j] + 1)
(단, 0 ≤ j < i, A[j] < A[i])
정답 = max(dp)
요약하면,
i보다 앞에서 값이 더 작은 j들을 모두 확인한 뒤
그중 dp[j]가 가장 큰 값을 골라 1을 더한다.
3. 이중 반복문을 떠올리는 로직
dp[i]를 구하는 데 필요한 값은 dp[0] ~ dp[i-1] 전체다.
즉,
"현재 i의 정답은 i보다 앞에 있는 모든 j를 대상으로 한다."
이 구조 때문에 반복문은 자동으로 아래 형태가 된다.
for i in range(N):
for j in range(i):
...
이 문제는 dp[i]가 “이전 전체 상태”에 의존하는 전형적인 DP다.
그래서 2중 반복문이 자연스럽게 강제된다.
4. DP에서 range를 잡는 기준
DP는 항상 “이 상태가 어디에서 왔는가?”를 먼저 말로 설명해야 한다.
원천(source)을 알면 반복문이 자동으로 결정된다.
대표 패턴:
1) dp[i]가 dp[i-1], dp[i-2] 등 ‘특정 몇 개’만 보면 됨
→ 단일 for i
2) dp[i]가 dp[0..i-1] 전체를 봐야 함
→ for i, for j in range(i)
3) 2차원 DP에서 dp[i][j]가 위·왼쪽에서 오면
→ 2중 for(i), for(j)
이 문제는 2번 패턴
i가 그 전까지의 값들을 봐야하니 j = 0~i-1 . 이중반복문 사용해야한다.
5. 해답 코드
import sys
input = sys.stdin.readline
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[j] + 1 = “누군가에게 붙이는 경우”
dp[i] = “붙일 데 없어서 혼자 서는 경우”
둘 중 큰 것을 선택 → max(dp[i], dp[j] + 1)
