백준 문제 풀이 - 가장 긴 증가하는 부분 수열 (11053 문제)
문제
문제 확인하기
풀이
증가하는 부분 수열이란 배열 arr이 주어졌을 때, 특정 몇몇 원소를 제외한 수열이 계속해서 이전 원소보다 큰 형태의 수열을 말한다.
예를 들어 { 1, 3, 7, 4, 2, 5, 6 } 이라는 배열이 있다고 하자.
이 배열에 대한 증가하는 부분 수열은
{ 1, 3, 7 }
{ 1, 3, 4, 5, 6 }
{ 1, 2, 5, 6 }
와 같은 수열이 될 수 있다.
가장 긴 증가하는 부분 수열이란, 위 증가하는 부분 수열들 중에서 가장 긴 길이의 수열을 말한다.
여기서는 { 1, 3, 4, 5, 6 } 수열이 길이 5로 가장 길기 때문에, 해당 수열이 가장 긴 길이의 수열이 된다.
어떻게 이를 구할 수 있을까?
내가 생각한 방법은 수열 arr이 주어졌을 때 수열의 i번째 원소인 arr[i]를 마지막 원소를 갖는 부분 수열의 최장 길이를 dp 테이블에 기록하는 것이다.
arr[i]가 부분 수열의 마지막 원소가 된다는 말은 부분 수열에서 가장 큰 값이라는 말이다.
dp 테이블의 값을 arr[i]로 하고, 인덱스를 부분 수열에서 arr[i]가 가장 큰 값일 때의 해당 부분 수열의 길이로 사용하도록 한다.
그리고 반복을 통해 수열 arr의 원소를 순차적으로 탐색하며 매 arr[i]마다 dp 테이블에 기록된 arr[i]보다 작은 값을 탐색하도록 한다.
탐색을 통해 찾은 값의 인덱스가 dp 테이블의 최고 인덱스와 같으면, arr[i]를 마지막 원소로 갖는 부분 수열의 길이는 현재 dp 테이블의 길이 + 1로 갱신된다.
또한, 동일한 부분 수열의 길이 k를 갖는 arr[i]는 서로 다른 여러 값이 존재할 수 있다.
예를 들어 { 1, 3, 7, 4, 2, 5, 6 } 배열에서 3번째 원소까지 탐색했다고 하자.
3번째 원소인 7이 마지막 원소인 부분 수열은 { 1, 3, 7 }로 길이는 3이다.
이번에는 4번째 원소를 탐색할 차례이다.
4번째 원소인 4가 마지막 원소인 부분 수열은 { 1, 3, 4 }로 길이는 3이다.
4와 7은 모두 길이가 3이다.
그러면 dp 테이블에는 4와 7중 어떤 값을 기록해야 할까?
dp 테이블에는 더 작은 값을 기록하는 것이 맞다.
아직 탐색하지 않은 원소 중 4보다 크고 7보다 작은 값이 존재할 때, 7을 선택하게 되면 해당 원소들은 증가하는 부분 수열의 원소가 될 수 없다.
따라서 최대한 긴 증가하는 부분 수열을 얻기 위해서는 k 길이를 갇는 arr[i]가 dp[k]에 기록된 값보다 작다면 dp[k]를 더 작은 값으로 갱신해주도록 한다.
말로 설명하는 것 보다 코드를 보는 것이 더 이해가 잘 될듯하니 코드를 살펴보자.
위 내용을 토대로 작성한 코드는 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
// 수열을 입력받기 위한 배열
private static int[] arr;
// dp[k]에서 k는 부분 수열의 길이를 의미.
// dp[k]는 k 길이의 부분수열 중 마지막 원소의 값
private static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new int[n+1];
dp = new int[n+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken());
// dp 테이블의 끝을 가리킴
int dpPointer = 0;
for (int i = 1; i <= n; i++) {
int tmpIdx = dpPointer;
// dp 테이블에서 arr[i]보다 작은 값이 기록된 인덱스를 찾는다.
while (tmpIdx > 0 && arr[i] <= dp[tmpIdx]) tmpIdx--;
// dp[tmpIdx] : arr[i]보다 작은 값.
// dp[tmpIdx + 1] : arr[i]보다 크거나 같은 값.
// tmpIdx + 1은 arr[i]를 마지막 원소로 하는 부분 수열의 길이.
// 길이가 같을 때, dp 테이블에 기록된 값이 arr[i]보다 크면, dp 테이블을 arr[i]로 갱신
if (dp[tmpIdx + 1] > arr[i]) dp[tmpIdx + 1] = arr[i];
// arr[i]보다 작은 값의 위치가 dp 테이블의 끝이라면
// arr[i]를 마지막 원소로 갖는 부분 수열이 가장 길기 때문에 dp 테이블 갱신
// dp 테이블의 끝을 1칸 증가시켜주고 해당 위치에 arr[i]를 기록
if (tmpIdx == dpPointer) dp[++dpPointer] = arr[i];
}
// dp 테이블의 끝을 가리키는 인덱스가 가장 긴 증가하는 부분 수열의 길이임.
System.out.println(dpPointer);
}
}