문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이를 구하는 문제다. 부분 수열은 원래 수열에서 일부 원소를 선택하되 순서를 유지한 것이며, 선택된 원소들이 순증가해야 한다.
입력
- 첫째 줄: 수열의 크기 N (1 ≤ N ≤ 1000)
- 둘째 줄: N개의 정수 A[i] (1 이상 1000 이하)
출력
가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 10 20 10 30 20 50 | 4 |
풀이
dp[n]을 n번째 원소를 마지막으로 하는 LIS의 최대 길이로 정의하고 Top-Down 메모이제이션으로 계산한다. n번째 원소보다 작은 이전 원소들에서 만들어지는 LIS에 1을 더한 값 중 최댓값이 dp[n]이다.
dp[0] = 1로 초기화한다 (첫 원소는 길이 1인 LIS).LIS(n)함수는 n번째 원소를 마지막으로 하는 LIS 최대 길이를 반환한다.dp[n]이 null이면 1로 초기화하고,i < n이면서arr[i] < arr[n]인 모든 i에 대해max(dp[n], LIS(i) + 1)을 계산한다.- 모든 n에 대해
LIS(n)을 호출하고dp[n]중 최댓값이 답이다.
핵심 아이디어: dp[n] = max(dp[i] + 1) (단, i < n이고 arr[i] < arr[n])이라는 LIS의 기본 점화식을 Top-Down으로 구현한다. Integer[] 타입으로 null을 활용해 미계산 상태를 표현한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Day72BOJ11053LISDP재귀 {
static int N, ans;
static int[] arr;
static Integer[] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
ans = 1;
st = new StringTokenizer(br.readLine());
arr = new int[N];
dp = new Integer[N];
dp[0] = 1;
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++)
LIS(i);
for (int i = 0; i < N; i++)
ans = Math.max(ans, dp[i]);
System.out.println(ans);
br.close();
}
// LIS : 최장 증가 부분 수열
private static int LIS(int n) {
if (dp[n] == null) {
dp[n] = 1;
for (int i = n - 1; i >= 0; i--)
if (arr[i] < arr[n])
dp[n] = Math.max(dp[n], LIS(i) + 1);
}
return dp[n];
}
}복잡도
- 시간: O(N^2) — 각 원소마다 이전 원소를 모두 확인
- 공간: O(N) — dp 배열과 입력 배열 각각 N 크기