[백준 14002] 가장 긴 증가하는 부분 수열4 / 자바 / dp

#문제         

레벨: G4
알고리즘: dp
풀이시간: 1시간
힌트 참조 유무:

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

---

#문제 풀이        

 

[1번째 시도: 실패]

멍청한 풀이. 시간복잡도 n으로 풀 수 있지 않을까? 그리드 형식으로 랭킹을 매기는 방식. 혹시 나와 같은 사람이 있을까봐 기입해두었다. skip해도 된다.

package project;

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));

        // 첫 번째 입력: 배열의 크기 n
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        // 두 번째 입력: 배열의 요소들
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        int max = arr[0];
        int maxInd = 0;
        int[] rank = new int[n];
        rank[0] = 1;
        int length = 1;

        // 최장 증가 부분 수열 계산
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] < arr[i])
                rank[i] = rank[i - 1] + 1;
            else {
                rank[i] = 1;
            }

            if (max < arr[i] && rank[maxInd]+1 >= rank[i]) {
                rank[i] = rank[maxInd] + 1;
                max = arr[i];
                maxInd = i;
            }

            length = Math.max(length, rank[i]);
        }

        System.out.println(length);

        int now = length;
        Stack<Integer> stack = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            if (rank[i] == now) {
                stack.push(arr[i]); // 스택에 값을 추가
                now--;
            }
        }

        // 스택에서 값을 꺼내어 출력
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
}

 

위 코드가 틀릴 예외상황은 아래와 같다.

input:
11       
1 3 2 4 3 5 4 1 3 4 5

output:
4
1 3 4 5

예상 정답:
1 2 3 4 5

 

---

 

LIS 문제는 dp로도 풀 수 있고 이분 탐색을도 풀 수 있다. 다만 차이는 있는데 이분탐색은 LIS의 길이는 정확하게 알려주지만 그 안에 담긴 배열은 정확하지 않을 수 있다. 이거에 관해서는 나중에 링크를 첨부하도록 하겠다. 본론으로 돌아와서, 남은 방법인 dp를 써서 풀이했다.

dp[i] = i인덱스가 가지는 LIS 순위이다.

순서대로 LIS 배열을 출력해야 하므로 dp를 완성 후 뒤에서부터 탐색하여 LIS 순위에 맞게 스택에 담아준다. 그리고 스택에서 꺼내 답을 순서대로 출력한다.

 

• 각 위치에서 끝나는 LIS의 길이를 계산한다.
• 이전의 모든 원소들을 검사하여 현재 원소보다 작은 값들 중 가장 긴 LIS를 찾고, 그 길이에 1을 더한다.
• 전체 배열에서 가장 긴 LIS의 길이를 찾는다.
• 역추적하여 실제 LIS를 구성한다.

 

 

---

#풀이 코드      

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        
        int[] dp = new int[n];
        int maxLength = 0;
        int maxIndex = 0;
        
        // dp를 사용하여 LIS 길이 계산
        // i인덱스의 배열값만 수정 j인덱스 배열값은 수정 안함( <- 개인적으로 dp 코드이해하는데 편함)
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                maxIndex = i;
            }
        }
        
        System.out.println(maxLength);
        
        // 스택을 사용하여 LIS 재구성
        Stack<Integer> stack = new Stack<>();
        int currentLength = maxLength;
        for (int i = maxIndex; i >= 0; i--) {
            if (dp[i] == currentLength) {
                stack.push(arr[i]);
                currentLength--;
            }
        }
        
        // LIS 출력
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
}