[Baekjoon]11053.가장 긴 증가하는 부분수열(DP)

Baekjoon

#11053. 가장 긴 증가하는 부분 수열

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

---

이 문제는 Longest Increasing Subsequence(LIS)로 유명한 문제라고 한다. 그 동안 풀었던 문제와는 다른 유형인 것 같아서 아이디어가 떠오르지 않았는데 유튜브에서 영상을 보고 바로 이해가 되어 풀 수 있었다. 이 영상이 도움이 되었다. 

영상에서 설명한 방법은 시간복잡도가 O(n^2) 이다. 그런데 n이 100,000 이상일때는 이 방법으로 풀 수 없다. 시간 복잡도 O(nlogn) 인 방법이 있는데 이번 포스팅에서는 먼저 O(n^2)인 방법으로 풀고 이후에 따로 O(nlogn) 방법을 공부하여 포스팅 해야겠다. 

먼저 배열 d를 정의하면

d[n] : 수열 a에서 n번째 수를 마지막 원소로 하는 증가하는 부분 수열의 최대 길이

(말로 풀어 쓰니까 이상하다..)

먼저 입력받은 수열을 저장할 배열 a를 생성하고 a와 같은 길이의 배열 d를 생성한다.

각 원소 하나는 길이가 1인 부분 수열이라고 할 수 있으므로 모든 d[n]에 대해 1로 초기화시킨다. 

위와 같이 a[n]과 d[n]을 생성하고 d[n]은 1로 초기화를 한다. i는 두번째 원소부터, j는 첫번째 원소부터 반복문을 돌기 시작한다. a[i]가 a[j] 보다 커야 증가하는 부분 수열이므로  그 때만 d[n] 의 갱신 조건을 살핀다.

위 그림에서 20은 10보다 크기때문에 증가하는 부분수열이다. 이 때 d[j]에 1을 더한 값이 a[j]부터 a[i]까지 부분 수열의 길이가 되는데 이것을 d[j]+1로 표현할 수 있다. 이 값이 d[i]보다 크면 d[i]를 이 값으로 갱신하고 아니면 그대로 둔다. 여기서 d[1]에 저장되는 값은 부분 수열 {10, 20}의 길이이다.

j는 i 전까지 반복문을 돌고 i가 이동한다. 위 그림에서 a[i]>a[j]가 아니므로 증가수열이 아니다. 따라서 건너뛴다.

위 그림에서 10<30 이므로 d[n]을 갱신할 후보가 된다. d[j]+1=2 >d[i]=1 이므로 d[i]를 2로 갱신한다. 이것은 부분 수열{10,30}의 길이이다. 

갱신된 d[3]=3 은 부분 수열 {10, 20, 30}의 길이이다. 

위 그림에서는 10<30 이지만 d[j]+1이 d[i]보다 작기때문에 갱신하지 않는다. 

이와 같은 과정을 i가 맨 마지막 원소인 50이 될 때까지 반복하면 다음과 같은 결과를 얻는다.

우리가 구하고자 하는 답은 d[n]의 최댓값이므로 5가 정답이 되고 이것은 부분 수열 {10, 20, 25, 30, 50}의 길이이다.

이 문제의 원리를 이용해서  가장 큰 증가 부분 수열, 가장 긴 감소하는 부분 수열, 가장 긴 바이토닉 수열 문제도 풀 수 있다. 

가장 큰 증가 부분 수열은 d[n]을 1대신에 a[n]의 각 원소로 초기화한 후 d[n]을 갱신할때  d[j]+1 이 아니라 d[j]+a[i] 값과 비교하여 갱신하는것이 다른 점이다. 가장 긴 감소하는 부분 수열은 단순히 a[i]와 a[j]를 비교할때 부등호 방향만 바꾸면 되는 문제였다. (감소수열을 찾는것이므로) 바이토닉 수열은 LIS를 양쪽 방향에서 모두 진행하는 아이디어가 필요했는데 이건 따로 포스팅을 하도록 해야겠다. 

<전체코드>

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

public class _11053 { 

	static int n;
	static int[] a;
	static int[] d;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		a = new int[n];
		d = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < n; i++) {
			d[i] = 1; // 초기화
		}

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (a[i] > a[j]) {
					if (d[i] < d[j] + 1) {
						d[i] = d[j] + 1;
					}
				}
			}
		}		
		System.out.println(max(d));
	}
	private static int max(int[] d) {
		int max = d[0];
		for (int i = 0; i < d.length; i++) {
			if (max < d[i]) {
				max = d[i];
			}
		}
		return max;
	}
}