[Java] 11053번 : 가장 긴 증가하는 부분 수열

[peppermintt0504]

문제 풀이

해당 문제는 DP 문제로 진행하면서 이전의 DP 중 가장 큰 값에 더해 나가며 진행하는 문제이다. 해당 문제는 DP문제로 분류되어 있지만 이분 탐색으로 푸는 문제이지만, 분류가 DP이므로 DP로 풀었다. 그렇기에 DP 문제인데도 불구하고 O(N*N)의 시간 복잡도를 가지고 있다.

위 예제의 수열은 {10, 20, 10, 30, 20, 50} 이다. 이를 seq라고 하고, dp[] 배열에 메모이제이션을 한다.

먼저 seq[0] = 10에 대한 수열을 찾아보면 seq[0]보다 이전 값은 없으므로 10 자체 하나밖에 존재하지 않으므로 dp[0] = 1 이 된다. 그 다음 seq[1] = 20에 대한 수열을 찾아보면 seq[0] = 10으로 20보다 작기 때문에 {10, 20} 이라는 부분수열이 되고, 길이는 2로 dp[1] = 2가 되는 것이다. seq[2] = 10의 경우 이전 값들 중 작은게 없으므로 {10} 하나만 되므로 dp[2] = 1이 되고.. 이런식으로 나가는 것이다.

그렇게 증가하는 수열을 구하면 다음과 같다.

즉 각 dp[] 의 길이들은 다음 부분 수열을 의미하는 것이다.

dp[0] = {10} : 길이 1

dp[1] = {10, 20} : 길이 2

dp[2] = {10} : 길이 1

dp[3] = {10, 20, 30} : 길이 3

dp[4] = {10, 20} : 길이 2

dp[5] = {10, 20, 30, 50} : 길이 4

풀이 코드

bottom-up (본인 풀이)

import java.util.*;
import java.io.*;
public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	
	public static void main(String[] args) throws IOException{
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] board = new int[T+1];
		int[] dp = new int[T+1];
		int max = 0;
		
		int count = 1;
		while(T-- > 0) {
			board[count] = Integer.parseInt(st.nextToken());
			count++;
		}count--;
		
		
		for(int i = 1 ; i <= count; i++) {
			dp[i] = 1;
			for(int j = 1; j <= i; j++) {
				if(board[j] < board[i] && dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;
				}
			}
			if(max < dp[i])max= dp[i];
		}
		System.out.println(max);
	}

}

(참고) top-down (출처 : https://st-lab.tistory.com/137)

static int LIS(int N) {
		
	// 만약 탐색하지 않던 위치의 경우 
	if(dp[N] == null) {
		dp[N] = 1;	// 1로 초기화 
			
		// N 이전의 노드들을 탐색 
		for(int i = N - 1; i >= 0; i--) {
			// 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
			if(seq[i] < seq[N]) {
				dp[N] = Math.max(dp[N], LIS(i) + 1);
			}
		}
	}
	return dp[N];
}

(참고) 이분 탐색 (출처 : https://st-lab.tistory.com/137)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
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());
		
		int[] seq = new int[N];
		int[] LIS = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		LIS[0] = seq[0];
		int idx = 1;
 
		for(int i = 1; i < N; i++) {
			if(LIS[idx - 1] < seq[i]) {
				LIS[idx++] = seq[i];
			}
			else if(LIS[0] > seq[i]) {
				LIS[0] = seq[i];
			}
			else {
				int temp = Arrays.binarySearch(LIS, 0, idx, seq[i]);
				LIS[temp < 0 ? -(temp + 1) : temp] = seq[i];
			}
		}
		System.out.println(idx);
	}
}