[BOJ] 백준 14002번 가장 긴 증가하는 부분 수열 4 LIS - DP (Java)

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

난이도 : 골드 4

유형 : LIS / DP

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

▸ 문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

▸ 입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

▸ 출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

문제 풀이  

백준 11053번 가장 긴 증가하는 부분 수열의 확장 문제이다. 수열의 최대 크기는 1,000으로 이중포문을 사용하여도 1,000^2으로 성능에 크게 상관없다.

 

dp는 1차원 배열로 수열의 증가하는 부분 수열의 크기를 저장해준다.

• dp[i] = arr[i]의 증가하는 부분 수열 크기

 

여기까지는 11053번 문제와 똑같다. 추가된 요구사항은 LIS 수열을 출력하는 것이다. 현재 가지고 있는 데이터 LIS최대 길이, arr, dp를 가지고 역추적하면 된다. 

설계

1. i : 1 ~ n-1
   1. 이전의 원소랑 비교를 하여야하기 때문에 1부터 탐색을 시작한다.
2. j : 0 ~ i-1 , arr[i] > arr[j]
   1. 원소를 비교하며 증가하는 부분 수열의 크기를 갱신해준다 dp[i] = Math.max(dp[i], dp[j]+1);
   2. lis 길이도 구해준다. lis = Math.max(lis, dp[i])
3. LIS 최대 크기와 Stack 자료구조를 사용하여 역추적을 통해 LIS 수열을 탐색한다. if(dp[i] == lis) s.push(arr[i])
4. Stack에 저장된 데이터를 출력해준다.

 

시뮬레이션

arr[i]	1	5	6	2	3	4
dp[i]	1	2	3	2	3	4

LIS 길이 : 4

• dp를 i: n-1 ~ 0으로 역순으로 탐색한다.
  • dp[5] == 4 , st.add(arr[5])
  • dp[4] == 3 , st.add(arr[4])
  • dp[3] == 3 , st.add(arr[3])
  • dp[0] == 3 , st.add(arr[0])

 

풀이 코드 

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 void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] dp = new int[n];
		dp[0] = 1;
		int lis = 1;
		for(int i=1; i<n; i++) {
			dp[i] = 1;
			for(int j=0; j<i; j++) {
				if(arr[i] > arr[j]) {
					dp[i] = Math.max(dp[i], dp[j]+1);
					lis = Math.max(lis, dp[i]);
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(lis+"\n");
		
		Stack<Integer> s = new Stack<>();
		for(int i=n-1; i>=0; i--) {
			if(dp[i] == lis) {
				s.push(arr[i]);
				lis--;
			}
		}
		
		while(!s.isEmpty()) {
			sb.append(s.pop()+" ");
		}
		System.out.println(sb.toString());
	}
}