[BOJ_14002/JAVA]가장 긴 증가하는 부분 수열 4

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

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

문제

풀이

해당 문제는 [가장 긴 증가하는 부분 수열]의 조금 더 심화된 문제이다.

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

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

최장 증가 부분 수열(LIS)알고리즘을 통해서 위의 문제(11053)를 풀었는데,

이번 문제는 LIS 알고리즘만 가지고는 풀리지 않았다. LIS알고리즘은 가장 긴 수열의 길이만 알 수 있었다.

수열을 출력까지 해야하기때문에 역추적이라는 개념을 사용해서 스택에 저장하고 그것을 출력하는 방식으로 해결하였다.

 

1. 이중 for문을 돌면서 dp[]배열을 채워주었다. 여기서 dp[]배열은 각 인덱스의 값까지 가장 긴 수열의 길이가 저장되어있다. 

i까지 자신이 앞에서 몇번째로 큰 숫자인지 판단하기 위해 for()문을 한개 더 사용하여 j와 i를 비교하도록 하였다.

2. dp배열을 채운 후에 뒤에서 부터 배열을 탐색하면서 역추적을 한다.

3. 지금 현재 가장 긴 수열의 길이(max)와 dp[i]같다면 dp[i]부터 시작한다. 스택에 실제 숫자를 push해준다.

이때 스택을 사용하는 이유는 역추적이기때문에 큰 수부터 집어넣기때문에 스택을 써야 출력할 때 작은 수부터 출력할 수 있기때문이다.

4. 그리고 max를 하나씩 줄이면서 dp[i]의 값와 같은 값을 하나씩 찾고 스택에 집어넣는다.

 

이해를 돕기위해 예를 들자면 {10 20 10 30 20 50}의 dp값은 [1,2,1,3,2,4}이다. max는 dp[5]의 값인 4이다.

dp[i]를 n-1부터 돌다가 max를 만나게 되는 순간부터 스택에 넣는다. dp[5]가 첫번째 경우일 것이고 스택에 입력숫자배열인 num[5]를 넣는다.

그리고 max--를 하면 max는 3가 되고 dp[3]이 이에 해당한다. 그러면 또 스택에 num[3]을 집어넣는다. 

그러면 스택에는 [50 30 20 10] 까지 들어가 있는 상태!

 

5. 스택이 빌 때까지 출력을 하면 완료!

 

코드

package Week07;

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

public class BOJ14002 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
	
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int num[]=new int[n];
		int dp[]=new int[n];
		
		for(int i=0;i<n;i++) {
			num[i]=Integer.parseInt(st.nextToken());
		}
		
		for(int i=0;i<n;i++) {
			dp[i]=1;
			
			for(int j=0;j<i;j++) {
				if(num[i]>num[j] && dp[j]+1>dp[i]) {
					dp[i]=dp[j]+1;
				}
			}
		}
		
		
		int max=dp[0];
		for(int i=0;i<n;i++) {
			if(max<dp[i]) {
				max=dp[i];
			}
		}
		sb.append(max+"\n");
		
		Stack<Integer> stack = new Stack<>();
		// dp역추적
		for(int i=n-1;i>=0;i--) {
			if(dp[i]==max) {
				stack.push(num[i]);
				max--;
			}
		}
		while(!stack.isEmpty()) {
			sb.append(stack.pop()+" ");
		}
		
		System.out.println(sb);

	}

}