백준 11053 - 가장 긴 증가하는 부분 수열(자바 - 동적 프로그래밍)

 

평범한 배낭 문제 이후 또 다시 마주친 동적 프로그래밍 응용 문제

위의 말에서 언급한 평범한 배낭 문제와 같이 또 한번 동적 프로그래밍의 역량 부족을 느낀 문제이다.

실버 2 라는 문제 난이도를 보고 그래도 쉽지 않을까 생각했으나 동적 프로그래밍 방식의 코딩에 대한 역량 부족은 문제의 난이도와는 별개였다.

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

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

 

입력으로 수열의 데이터가 들어왔을때, 해당 수열의 값이 증가하는 부분 수열 중에서 가장 길이가 긴 수열의 길이 값을 반환하는 문제이다.

처음 이 문제를 풀 때는 그냥 일단 수열을 정렬한 다음, 중복되는 숫자들을 제거 해주면 그게 바로 가장 긴 증가하는 부분 수열이 아닌가 생각하고 코딩을 해봤지만 언제나 그렇듯 그건 틀린 생각이었다.

 

결국 이 문제도 패스트 캠퍼스의 해설 강의를 참조하게 되었다.

진짜 동적 프로그래밍은 조금만 문제가 응용되서 나와도 도대체 점화식을 어떻게 짜야 할지 도통 감이 오질 않는것 같다.

 

핵심 아이디어

- D[i] = array[i] 를 마지막 원소로 가지는 부분 수열의 최대 길이를 구한다.

- 모든 0 <= j < i 에 대하여 D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

 

- Main.java

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 Main {
	// 전형적인 동적 프로그래밍 문제
	// 수열의 크기가 N일 때, 기본적인 동적 프로그래밍 알고리즘으로 O(N^2) 에 해결할 수 있다.
	/*
	 * D[i] = array[i] 를 마지막 원소로 가지는 부분 수열의 최대 길이
	 * 모든 0 <= j < i 에 대하여, D[i] = max(D[i], D[j]+1) if array[j] < array[i]
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int arraysize = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int[] array = new int[arraysize];
		
		for(int i = 0; i < arraysize; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] dp = new int[arraysize];
		for(int i = 0; i < dp.length; i++) {
			dp[i] = 1;
		}
		
		for(int i = 1; i < arraysize; i++) {
			for(int j = 0; j < i; j++) {
				if(array[j] < array[i])
					dp[i] = Math.max(dp[i], dp[j]+1);
			}
		}
		
		bw.write(Arrays.stream(dp).max().getAsInt() +"\n");
		bw.flush();
		bw.close();
		
	}
}