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

백준 11722번 :: 가장 긴 감소하는 부분 수열

---

백준 온라인 저지 11722번 - 가장 긴 감소하는 부분 수열

Java 알고리즘 문제풀이

풀이

DP(다이나믹 프로그래밍) 문제입니다.

큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘인데, 코딩테스트에 자주 출제되는 문항입니다.

 

문제를 해석해보면

• 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구한는 문제
• 수열 A = 일때
• 가장 긴 증가하는 수열

 

DP(다이나믹 프로그래밍)에서 중요한 것은 규칙을 찾거나, 어떤 일반식을 찾는 것이 키 포인트이다.

 

이제 문제를 작게 쪼개서 생각해보자

 

먼저 A수열의 A[1], A[2], A[3]를 먼저 보자. A[2]보다 A[3]가 작기때문에 D[2]값에 +1을 해준다.

두 번째로 A[4]를 진행한다. 이때 A[4]의 값은 A[2]보다 작고 A[3]보다 크다 그런데 어처피 A[3]보다 크기때문에 D의 값은 2를 가지게 된다.

세 번째로 A[5]를 진행한다. A[5]는 이전 A[4]와 같은 값이다. 따라서 D[4]의 값을 복사한다.

마지막으로 A[6]의 값이 가장 작고, 이전 값인 A[5]의 값은 A[6]보다 크다. 이때 D[5]의 값에 +1을 해준다.

문제를 풀면서 마지막 값만을 출력하는 것을 주의해야한다. 마지막에는 전체 D[i]값을 조사해서 제일 큰 값을 출력해야한다.

import java.util.Scanner;

public class Beak11722 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int arr[] = new int[n + 1];
        int d[] = new int[n + 1];

        for (int i = 1; i <= n; i++)
            arr[i] = sc.nextInt();

        d[1] = 1;

        for (int i = 2; i <= n; i++) {
            d[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] < arr[j] && d[i] <= d[j]) {
                    d[i] = d[j] + 1;
                } else if (arr[i] == arr[j]) {
                    d[i] = d[j];
                }
            }
        }

        int max = 0;

        for (int i = 1; i <= n; i++)
            max = Math.max(d[i], max);

        System.out.println(max);

        sc.close();
    }
}​