11053 - 가장 긴 증가하는 부분 수열[S2]

 

문제

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

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

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

풀이

가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS) 문제로, 가장 유명한 dp 문제라고 한다.

나의 풀이의 경우, dp의 경우 '증가 부분 수열의 수치' , arr의 경우 기존 입력 배열값을 사용하였다.

 

N번째 증가 수치(dp)를 확인하기 위해 N-1번째까지의 가장 많은 값을 가지고 있는 dp값을 확인하였고,

또한 arr 값 역시 arr[N]보다 낮은 값임을 확인하였다.

 

코드

 

import java.util.*;
import java.io.*;
class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] dp, arr;
    public static void main(String[] args) throws Exception {
    	int N = Integer.parseInt(br.readLine());
    	
    	dp = new int[N]; 
    	arr = new int[N];
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
    	
    	for(int i = 0; i < N; i++) {
    		dp[i] = check(i, arr[i]) + 1; //dp 배열에 LIS 개수 갱신
    	}
    	
        // 모든 dp 값 중 최대값 찾기
        int max = 0;
        for (int i = 0; i < N; i++) {
            if(dp[i] > max) max = dp[i];
        }

        System.out.println(max);
    }
    
    static int check(int idx, int value) {
    	int res = 0;
    	
    	for(int i = 0; i < idx; i++) {
    		if(dp[i] > res && arr[i] < value) res = dp[i];
    	}
    	return res;
    }
} //EOC