[Algorithm/Java] 백준 11053번 - 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053
📌 문제
문제 유형
- DP
📘 문제 설명
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
📥 입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
6
10 20 10 30 20 50
📥 출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
4
🧠 선행 지식
LIS(최장 증가 부분 수열)
이런 문제를 LIS(최장 증가 부분 수열) 이라고 한다.
주어진 수열에서, 순서를 바꾸지 않고 오름차순으로 구성 가능한 원소를 골라 가장 길게 증가하는 수열을 찾는 문제이다.
LIS 문제를 해결하는 방법은 여러 가지가 있지만, 가장 일반적인 방법은 동적 계획법 (DP)과 이분 탐색을 활용하는 방법이 존재한다.
예제
주어진 수열이 [10, 20, 10, 30, 20, 50]이라면, 가장 긴 증가하는 수열은 [10, 20, 30, 50]이고, 그 길이는 4이다.
dp[i]는 i번째 원소를 끝으로 하는 가장 긴 증가하는 부분 수열의 길이를 의미한다.
dp[0] = {10} : 길이 1
dp[1] = {10, 20} : 길이 2
dp[2] = {10} : 길이 1
dp[3] = {10, 20, 30} : 길이 3
dp[4] = {10, 20} : 길이 2
dp[5] = {10, 20, 30, 50} : 길이 4
💻 전체 코드
- i는 현재 원소를 가리키고, j는 i보다 이전에 있는 원소들을 나타낸다.
- 원소와 이전의 모든 원소들을 비교하여 LIS를 확장한다.
- 즉, j는 i번째 원소보다 앞선 원소들을 하나씩 비교하면서,
arr[i]보다 작은arr[j]를 찾아서 LIS를 확장할 수 있는지를 판단한다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n+1];
int[] dp = new int[n+1]; // 가장 긴 수열의 길이
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
// LIS 계산
int max = 0;
for (int i = 0; i < n; i++) { // i 이전의 원소들과 비교
dp[i] = 1; // 최소 자기 자신만 포함된 수열
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1); // LIS 길이 갱신
}
}
max = Math.max(max, dp[i]); // 가장 긴 LIS 길이 갱신
}
System.out.println(max);
}
}
댓글남기기