[백준/Java] 11722번 가장 긴 감소하는 부분 수열

문제 분석

부분 수열 문제는 보통 DP로 해결한다. 해당 문제의 경우, 감소하는 부분 수열의 최대값을 찾아야 한다. DP는 기본적으로 큰 문제를 작은 문제로 분할하는 것으로, 주어진 입력값이 작을 때 부터 차례로 값을 찾아야 한다. 

특정 위치를 기준으로 다음 값을 판단한다. 다음 값이 현재 값보다 크면 감소하는 수열에 해당하지 않고, 현재 값보다 작은 경우 감소하는 수열에 해당한다. 결국 다음값이 현재 값보다 큰 경우 새로운 부분 수열이 시작할 수 있고, 다음 값이 현재 값 보다 작은 경우 기존 부분 수열의 길이가 하나 증가된다.

위와 같은 규칙을 고려하여 알고리즘을 작성하자. 특정 위치를 기준으로 생각했을 때, 감소 수열의 최대 길이를 판단하기 위해서는 자신의 값보다 순서상 앞에 있는 수들이 몇개가 있는지 생각해야 한다. 또한 여러가지 감소하는 부분 수열이 존재하는 경우 해당 수열 중 최대 길이를 갖는 값을 dp에 저장해야 하므로 dp[j] + 1 >= dp[i] 조건을 추가해준다.

 

문제 풀이

import java.util.Scanner;

public class Main {

    static int N;
    static int[] dp;
    static int[] numbers;

    public static void main(String[] args) {
        input();
        setDp();
        output();
    }

    public static void input() {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        dp = new int[N];
        numbers = new int[N];

        for (int i = 0; i < N; i++) {
            numbers[i] = sc.nextInt();
        }
    }

    public static void setDp() {
        dp[0] = 1;
        for (int i = 1; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (numbers[i] < numbers[j] && dp[j] + 1 >= dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }

    public static void output() {
        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
    }
}