[백준] 14002번 - 가장 긴 증가하는 부분 수열 4

 

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

 

 

 

 

 

이전에 풀이한 백준 11053번 가장 긴 증가하는 부분 수열 문제의 풀이에 가장 긴 증가하는 부분 수열의 인덱스를 저장해주는 개념을 적용하면 풀이할 수 있다.

만약 백준 11053번을 아직 해결하지 않았다면 먼저 해결하고 오는 것이 도움이 될 것이다.

 

백준 11053번 풀이

[백준] 11053번 - 가장 긴 증가하는 부분 수열

 

 

 

백준 11053번에서 추가된 내용은 다음과 같다.

 

1. 수열 A를  반복하며 LIS의 최장 길이 max를 갱신하는 과정에서 만약 max를 갱신할 수 있다면 해당 부분 수열의 마지막 요소 인덱스를 idx에 저장한다. 이는 추후 LIS의 구성 요소를 거꾸로 찾아가기 위한 시작점이 될 것이다. 

 

2. 인덱스 i까지의 최장 부분 수열을 찾는 함수 LIS에서 최장 부분 수열 길이를 갱신할 수 있다면 dp에 LIS길이와 함께 이전 요소의 인덱스도 저장한다. 1번에서 저장한 idx를 출발점으로 하여 2번에서 저장한 이전 요소를 역으로 추적하여 최종적으로 LIS를 구성하는 부분 수열의 구성을 알아낼 수 있다.

 

// 수열 A를 완전 탐색하여 최장 부분 수열의 길이(LIS)를 갱신하고 LIS의 가장 마지막 인덱스를 idx에 저장한다.
Integer idx = 0;
int max = 0;

for (int i = 0; i < N; i++) {
    if (max < LIS(i)) {
        max = LIS(i);
        idx = i;
    }
}

// LIS를 역행하며 구성 요소를 찾아야 하므로 stack에 담아준 후 다시 꺼내면서 출력한다.
while (idx != null) {
    stack.push(idx);
    idx = dp[idx][1];
}



static int LIS (int idx) {
        
        if (dp[idx][0] == null) {
            
            dp[idx][0] = 1;
            
            int i = idx - 1;
            
            while (i >= 0) {
                
            	int temp = 0;
            	
            	if (A[idx] > A[i]) {
            		temp = LIS(i) + 1;
            		
                    // 만약 수열의 idx 까지의 요소의 최대 부분 수열 길이를 갱신할 수 있다면 idx 이전 부분 수열의 인덱스를 배열에 저장한다. 
	                if (temp > dp[idx][0]) {
	                    dp[idx][0] = temp;
	                    dp[idx][1] = i;
	                }
            	}
                
                i--;
            }
        }
        
        return dp[idx][0];
    }

 

 

 

 

 

 

 

 

 

 

전체 코드

import java.util.*;

public class Main {
    
    static int N, A[];
    static Integer dp[][];
    
    public static void main (String[] args) {
        

// 입력 시작
        Scanner sc = new Scanner(System.in);
        
        
        N = sc.nextInt();
        
        
        A = new int[N];
        
        for (int i = 0; i < N; i++) A[i] = sc.nextInt();
        
// 입력 끝

        dp = new Integer[N][2];
        
        Integer idx = 0;
        int max = 0;
        
        for (int i = 0; i < N; i++) {
            if (max < LIS(i)) {
                max = LIS(i);
                idx = i;
            }
        }
        
        
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack();
        
        sb.append(max + "\n");
        
        while (idx != null) {
            stack.push(idx);
            idx = dp[idx][1];
        }
        
        while (!stack.isEmpty()) {
        	int index = stack.pop();
        	sb.append(A[index] + " ");
        }
        
        
        System.out.println(sb);
        
        
        sc.close();
    }
    
    
    static int LIS (int idx) {
        
        if (dp[idx][0] == null) {
            
            dp[idx][0] = 1;
            
            int i = idx - 1;
            
            while (i >= 0) {
                
            	int temp = 0;
            	
            	if (A[idx] > A[i]) {
            		temp = LIS(i) + 1;
            	
	                if (temp > dp[idx][0]) {
	                    dp[idx][0] = temp;
	                    dp[idx][1] = i;
	                }
            	}
                
                i--;
            }
        }
        
        return dp[idx][0];
    }
}