[백준] 14002 가장 긴 증가하는 부분 수열 4 - DP + Stack + LIS JAVA

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

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

코드설명

DP와 Stack과 LIS(Longest Increasing Subsequence)  문제입니다.

 

처음에 

 A = {10, 20, 10, 30, 20, 50} 가 있을때

dp[] = {1, 2, 2, 3, 3, 5} 이런식으로 갱신하여서 for문으로 값이 변화하는 구간을 찾아서 진행하려고 하였지만

 

우리가 구하는것은 각 위치에서의 수열의 증가부분수열의 개수이므로

A = {10, 20, 10, 30, 20, 50} 이 있을때

dp[] = {1, 2, 1, 3, 2, 4} 이런식으로 구하는것이 더 적합합니다.

 

위의. 로직을 구현해보았습니다.

또한 Stack을 활용하여 DP Max값인 4를 기준으로 4 -> 3 -> 2 -> 1 을 찾아나가면서 Stack에 넣고,

10 20 30 50 출력하도록 합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	public static int N;
	public static int[] dp;
	public static int[] arr;
	public static int maxValue = 0;
	public static int answer;
	public static Stack<Integer> stack = new Stack<Integer>();
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[1001];
    	arr = new int[1001];
    	st = new StringTokenizer(br.readLine());
    	for(int i=1;i<=N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	for(int i=1; i<=N;i++) {
    		dp[i] = 1;
    		for(int j=1; j<i;j++) {
    			if(arr[j] < arr[i]) {
    				dp[i] = Math.max(dp[i], dp[j] + 1);	
    			}
    		}
    	}
    	
    	for(int val : dp) {
    		answer = Math.max(answer, val);
    	}
    	System.out.println(answer);
    	
    	//값을 찾기 위해 맨뒤에서부터 순서대로 찾아갑니다. 가장 큰 길이 -> 그 다음 큰 길이 -> ... ( ex. 4 -> 3 -> 2 -> 1 )
    	int value = answer;
    	for(int i=N;i>=1;i--) {
    		if(value == dp[i]) { //가장 큰 DP값
    			stack.add(arr[i]);
    			value -= 1;
    		}
    	}
    	while(!stack.isEmpty()) {
    		System.out.print(stack.pop()+" ");
    	}
    	
    	
    }
}

 

다르게 풀어본 코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    public static int N;
    public static int[] A;
    public static int[] cache, choices;
    
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        cache = new int[N + 1];
        choices = new int[N + 1];
        A = new int[N];
        
        Arrays.fill(cache, -1);
        Arrays.fill(choices, -1);
        
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
        	A[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(LIS(-1) - 1);
        ArrayList<Integer> arr = new ArrayList<Integer>();
        reconstruct(-1, arr);
        for(int v : arr) {
        	System.out.print(v+" ");
        }
    }
    
    public static int LIS(int start) {
    	
    	int ret = 1;
    	int bestNext = -1;
    	if(cache[start + 1] != -1) return cache[start + 1];
    	for(int next = start + 1; next < N ; next++) {
    		if(start == -1 || A[start] < A[next]) {
    			int cand = LIS(next) + 1;
    			if( ret < cand) {
    				ret = cand;
    				bestNext = next;
    			}
    		}
    	}
    	choices[start + 1] = bestNext;
    	return cache[start + 1] = ret;
    }
    
    public static void reconstruct(int start, ArrayList<Integer> seq) {
    	if(start != -1) {
    		seq.add(A[start]);
    	}
    	
    	int next = choices[start + 1];
    	if(next != -1) reconstruct(next, seq);
    }


}