[백준(baekjoon) 11722] 가장 긴 감소하는 부분 수열

문제

백준 11722

n(1…1,000)과 n의 크기를 가진 수열이 주어질 때,
수열에서 감소하는 부분 수열 중 가장 긴 길이를 출력.

• 예시 : A = {10, 30, 10, 20, 20, 10} 인 경우, A = {30, 20, 10} 이고 길이는 3이다.

해결

가장 긴 증가하는 부분과 매우 유사한 문제이다.

2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다.
최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다.

알고리즘

DP로 풀었고, bottom-up 방식으로만 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.
7.        int n = sc.nextInt();
8.        int[][] dp = new int[n][2];
9.        int maxLength = 1;
10.
11.        for (int i = 0; i < n; i++) {
12.            dp[i][0] = sc.nextInt();
13.            dp[i][1] = 1;
14.            for (int j = 0; j < i; j++) {
15.                if (dp[j][0] > dp[i][0])
16.                    dp[i][1] = Math.max(dp[i][1], dp[j][1] + 1);
17.            }
18.            maxLength = Math.max(maxLength, dp[i][1]);
19.        }
20.
21.        System.out.println(maxLength);
22.    }
23.}

결과