[알고리즘 - 백준] 14002번 가장 긴 증가하는 부분수열4(java)

백준 가장 긴 증가하는 부분수열4 - 문제 링크

이번 문제는 백준 11053번 가장 긴 증가하는 부분 수열의 확장문제로, 링크는 여기다.

위 문제와 차이점이 있다면 가장 긴 증가하는 부분 수열의 원소를 오름차순으로 출력해줘야한다는 점이 추가되었다.

풀이 로직

1. 인덱스 i = 1번부터 i = N-1번(입력받은 배열에서 마지막 인덱스)까지 차례대로 j = 0부터 j = i-1 를 돌면서 arr[i]>arr[j]인 경우를 찾아본다.

1번을 만족한다면, 2번으로 간다.

2. dp[i] = Math.max(dp[i], d[j]+1) 로 dp[i] 값을 갱신해준다. 또한 LIS = Math.max(LIS, dp[i])로, LIS값을 갱신된 dp[i]값으로 초기화해준다.

➡️ 여기서 dp[i] 값은 "현재 위치에서 가장 긴 증가하는 부분 수열의 길이"를 저장한다.
➡️ 여기에서 LIS값은 long타입으로, "현재까지 가장 긴 증가하는 부분 수열의 길이"을 의미한다. dp[i]와 헷갈릴 수도 있는데, dp[i]는 해당 위치, arr[i]값이 몇번째로 증가하는지만을 나타내기 때문에 조금의 차이점이 있다.

3. LIS는 현재 가장 긴 부분 수열의 길이값이 저장되어 있기 때문에 n-1부터 차례대로 0까지 for문을 돌며 LIS == dp[i]인 곳을 찾는다. LIS == dp[i]이라면 Stack에 arr[i]값 추가해주고 LIS-- 를 해준다.

4. 스택에 들어간 값을 차례대로 출력하면 끝

import java.util.*;
import java.io.*;
class Solution{
	static int arr[];
	static long dp[], LIS;
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		arr = new int [n];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dp = new long[n];
		dp[0] = 1;
		LIS = 1;
		for(int i=1;i<n;i++) {// arr[i] - 뒤의 값
			dp[i] = 1;
			for(int j=0;j<i;j++) { //arr[j] - 앞의 값
				if(arr[i]>arr[j]) {
					dp[i] = Math.max(dp[i], dp[j]+1);
					LIS = Math.max(LIS, dp[i]);
				}
			}
		}
		
		Stack<Integer> s = new Stack<>();
		for(int i=n-1;i>=0;i--) {
			if(LIS == dp[i]) {
				s.add(arr[i]);
				LIS--;
				if(LIS == 0) break;
			}
		}
		
		int size = s.size();
		sb.append(size).append("\n");
		for(int i = 0;i<size;i++) {
			sb.append(s.pop()).append(" ");
		}
		
		
		System.out.println(sb);
		
	}
}