BOJ11053_가장 긴 증가하는 부분 수열

개요

LIS(최장 증가 부분수열)에 대해 알아보고 문제도 풀어보자

문제접근

수열 A의 크기 : $1 \leq N \leq 1,000$
수열 A를 이루고 있는 A$_{i}$ : $1 \leq A_{i} \leq 1,000$
시간 제한 : 1초

이 문제를 처음 접했을 땐 케이스를 하나씩 비교하는 식만 흐릿하게 생각이 났다. 도저히 이 문제에 대해서 번뜩이는 아이디어가 생각나지 않았고 그래서 문제에 대해 알아보고 내가 나름대로 해석한 것을 작성해보겠다.

우선 이 문제는 다이나믹 프로그래밍과 이진 탐색으로 접근이 가능하다 하지만 이번 포스트는 다이나믹 프로그래밍으로 구현한 식에 대해서 다루겠다.

코드를 먼저 보겠다

package etc;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q11053 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int[] dp = new int[n];

		StringTokenizer st = new StringTokenizer(br.readLine());
		int max = Integer.MIN_VALUE;

		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			dp[i] = 1;
			for(int j = 0; j < i; j++) {
            
				if(arr[i] > arr[j])
					dp[i] = Math.max(dp[i], dp[j] + 1);
			}
			max = Math.max(max, dp[i]);
		}
		bw.write(Arrays.toString(dp)+"\n");
		bw.write(max + "");
		bw.close();
	}

}

이 부분을 주목해보자

if(arr[i] > arr[j])
	dp[i] = Math.max(dp[i], dp[j] + 1);

$arr[i]$ 가 $arr[j]$보다 크다면 $dp[i]$를 $dp[i]$ , $dp[j]$+1 중 큰 수를 담는다.

즉, 반복해오는 과정에서 '현재' 수가 '이전' 수 보다 큰지 기억 하면서 반복문을 통과하게 된다.

값을 기억함으로서 증가하는 수열의 최대 길이를 알 수 있게 되는 것이다.

시간복잡도는 모든 경우의 수를 비교하기에 $O(N^{2})$이다