[백준/JAVA] 11053: 가장 긴 증가하는 부분 수열

[백준/JAVA] 11053: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구해야 한다.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 30, 50} 이고, 길이는 4이다.

n까지 배열을 순회하는데(for -> i)
2중 for문으로 i 이전의 배열을 순회한다.(for -> j) 이 때 arr[j]가 arr[i]보다 작다면 증가하는 부분 수열이 될 수 있는 것이므로 dp[i] = dp[j] + 1로 교체해준다.(이전 길이에 1 추가한 것을 현재 길이로) 이는 이전 값을 활용해 현재 값을 구할 수 있는 bottom up 방식의 동적 프로그래밍 알고리즘 기법이다.

소스코드

---

import java.util.*;
import java.io.*;

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 arr[] = new int[n];
        int dp[] = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<n; i++)
        	arr[i] = Integer.parseInt(st.nextToken());
        
        dp[0] = 1;
        for (int i=1; i<n; i++) {
        	dp[i] = 1; // dp[x] = x에서 시작하는 증가 부분 수열의 최대 길이
        	for (int j=0; j<i; j++) {
        		if (arr[i] > arr[j])
        			// dp[j]+1가 더 긴 경우에만 교체해준다.
        			dp[i] = Math.max(dp[i], dp[j] + 1);
        	}
        }
        
        int result = 0;
        for (int i=0; i<n; i++)
        	result = Math.max(result, dp[i]);
        System.out.println(result);
    }
}