[백준][골드 4][DP] 14002. 가장 긴 증가하는 부분 수열 4

💡 다이나믹 프로그래밍 O(n(n+1)/2)

[문제]

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

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

 

[풀이]

O(nlog n)의 시간복잡도를 가지는 이분탐색 활용 최장 증가 부분 수열 알고리즘(LIS)으로도 이 문제를 풀 수 있지만 

가장 긴 증가하는 부분 수열, 가장 긴 증가하는 부분 수열 2, 가장 긴 증가하는 부분 수열 3, 가장 긴 증가하는 부분 수열 5 비슷한 유형의 문제를 이미 LIS 알고리즘으로 풀었다. 그래서 다른 방식의 문제 접근을 해보았다.

1. 0부터 자신 앞 범위까지의 값을 이용하는 다이나믹 프로그래밍 풀이 O(n(n+1)/2) (가우스 덧셈)
2. 앞의 값(inputList[j]) 중 자신보다 작은 값이며, 이전에 저장해놓은 사이즈(len)보다 현재 살펴보는 값(list[j])의 사이즈가 크다면
3. 사이즈를 저장해놓고, 해당 리스트(list[j])를 현재 리스트에 복사한다.
4. 작은 값이면서, 가장 긴 길이의 하위 리스트를 가지게 되며, 현재 값을 추가한다.
5. 최장 길이가 갱신될 때 해당 리스트를 기억해놓고, 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
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[] inputList = new int[N];
		int maxLen = 0;
		ArrayList<Integer> printList = new ArrayList<>();
		
		ArrayList<Integer>[] list = new ArrayList[N];
		for (int i = 0; i < N; list[i++] = new ArrayList<>());
		
		for (int i = 0; i < N; i++) {
			int v = Integer.parseInt(st.nextToken());
			inputList[i] = v;
			
			int len = 0;
			for (int j = 0; j < i; j++) {
				// 앞의 값(inputList[j]) 중 자신보다 작은 값이며
				// 이전에 저장해놓은 사이즈(len)보다 현재 살펴보는 값(list[j])의 사이즈가 크다면
				if(inputList[j] < v && len < list[j].size()) {
					// 사이즈를 저장해놓고
					len = list[j].size();
					// 해당 리스트(list[j])를 현재 리스트에 복사
					list[i] = (ArrayList<Integer>) list[j].clone();
				}
			}
			list[i].add(v); // 현재 값 추가
			if(maxLen < list[i].size()) {
				maxLen = list[i].size();
				// 최장 길이 갱신 시 해당 리스트 printList에 기억
				printList = list[i];
			}
		}

		StringBuilder sb = new StringBuilder();
		sb.append(maxLen + "\n");
		for(int e : printList) sb.append(e + " ");
		System.out.print(sb);
	}
}

 

[결과]

---

백준(BOJ) 문제 중 [ 14002. 가장 긴 증가하는 부분 수열 4 ] 문제를 풀고 정리한 내용입니다.