[백준11053, Java] 가장 긴 증가하는 부분수열

1. 문제

www.acmicpc.net/problem/11053

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

2. 문제풀이

• 브루트포스로 풀 경우, 시간 복잡도가 2의 N제곱이 되므로 시간 초과가 난다. ( numArray를 순회하며 해당 index를 선택한다, 하지 않는다로 구현한다. 선택할 때 오름차순 인지 검사한다. 그 후 선택할 index가 numArray의 크기를 넘어가면 numArray의 총합을 구한다)

• f(n) 을 numArray의 index가 n까지 증가하는 부분수열 중 가장 긴 부분수열의 길이라고 정의하자. 그러면 f(n) = Max( f(n-m) +1 , f(n) ) (m<n, numArray[m] < numArray[n])

• numArray[n]이 증가하는 수열의 첫번째 인 경우 증가하는 부분수열의 길이는 1이므로 f(n) 을 1로 초기화 한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] numArray;
    public static int[] memo;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        numArray = new int[N];
        memo = new int[N];

        st = new StringTokenizer(br.readLine()," ");
        for(int index = 0 ; index<N; index++){
            numArray[index] = Integer.parseInt(st.nextToken());
        }

        calculateLIS();
        int result = getLIS();
        bw.write(String.valueOf(result));
        bw.flush();
    }

    // memo[i] = numArray의 i 가장 긴 증가하는 부분수열
    // memo[i] = MAX(memo[i-j] +1 , memo[i]) ( numArray[i] > numArray[j] && i>j)
    public static void calculateLIS(){
        for(int i = 0 ; i< N; i++){
            memo[i] = 1;
            for(int j = i-1; j>=0; j--){
                if(numArray[i] > numArray[j]){
                    memo[i] = Math.max(memo[j]+1, memo[i]);
                }
            }
        }
    }

    public static int getLIS(){
        int result = memo[0];
        for(int index = 1; index<N; index++){
            result = Math.max(memo[index], result);
        }
        return result;
    }
}