14002번: 가장 긴 증가하는 부분 수열 4

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이와 그 수열 자체를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어집니다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어집니다.
• 출력: 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력합니다. 둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력합니다.

링크: https://www.acmicpc.net/problem/14002

풀이: 다이나믹 프로그래밍(DP)과 배열을 활용한 역추적

가장 긴 증가하는 부분 수열(LIS)의 길이를 구하는 기존 DP 방식에, 해당 수열이 어떤 경로로 완성되었는지 추적하기 위한 pre 배열을 추가로 도입하는 방식입니다.

• 상태 정의: d[i]는 $i$번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 의미합니다.
• 경로 기록: pre[i] 배열을 선언하여, d[i]가 갱신될 때마다 현재 원소 앞에 위치하게 된 이전 원소의 인덱스 j를 기록합니다.
• 초기화 주의사항: 이전 원소가 존재하지 않는 경우(본인이 수열의 시작점인 경우)를 식별하기 위해, pre 배열의 모든 값을 사전에 -1로 초기화해 두어야 합니다.
• 역추적 및 출력: 전체 탐색이 끝나면 LIS 길이가 최대인 시점의 인덱스 maxIdx부터 시작합니다. maxIdx를 pre[maxIdx]로 계속 업데이트하며 -1이 나올 때까지 거슬러 올라갑니다. 이렇게 찾은 수열은 뒤에서부터 앞으로 추적된 역순이므로, 리스트에 담은 뒤 거꾸로 출력하여 정답을 완성합니다.

코드

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));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       int[] a = new int[n];
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(st.nextToken());
       }

       int[] d = new int[n];
       int[] pre = new int[n];
       
       // 경로가 없는 경우를 위해 -1로 사전 초기화
       Arrays.fill(pre, -1);

       d[0] = 1;
       int ans = 1;
       int maxIdx = 0;
       
       for (int i = 1; i < n; i++) {
          d[i] = 1;
          for (int j = 0; j < i; j++) {
             // 현재 원소가 이전 원소보다 크고, 길이가 더 길어지는 경우 갱신
             if (a[j] < a[i]) {
                if (d[i] < d[j] + 1) {
                   d[i] = d[j] + 1;
                   pre[i] = j; // 이전 인덱스 기록
                }
             }
          }
          // 전체 최댓값 및 해당 인덱스 갱신
          if (ans < d[i]) {
             ans = d[i];
             maxIdx = i;
          }
       }

       bw.write(ans + "\n");
       
       // 역추적
       List<Integer> list = new ArrayList<>();
       while (maxIdx != -1) {
          list.add(a[maxIdx]);
          maxIdx = pre[maxIdx];
       }

       // 역순으로 탐색되었으므로 뒤에서부터 출력
       for (int i = list.size() - 1; i >= 0; i--) {
          bw.write(list.get(i) + " ");
       }

       bw.flush();
    }
}

알고리즘 분류

다이나믹 프로그래밍 (Dynamic Programming), 역추적 (Backtracking)