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

가장 긴 감소하는 부분 수열

1 초	256 MB	35656	22088	18169	62.951%

문제

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

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 30 10 20 20 10

예제 출력 1 복사

3

코드

package 가장긴감소하는부분수열;

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());        // 첫 번째 줄에서 수열의 크기 N을 입력받습니다.

        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken()); // 두 번째 줄에서 수열 A를 입력받습니다.
        }

        // 가장 긴 감소하는 부분 수열의 길이를 계산하여 출력합니다.
        int result = longestDecreasingSubsequence(A);
        System.out.println(result);
        br.close();
    }

    // 주어진 수열 A에서 가장 긴 감소하는 부분 수열의 길이를 계산하는 함수
    public static int longestDecreasingSubsequence(int[] A) {
        int N = A.length;

        // lds 배열을 생성하여 각 위치에서 끝나는 가장 긴 감소하는 부분 수열의 길이를 저장합니다.
        int[] lds = new int[N];

        // 모든 원소의 lds 값을 1로 초기화합니다.
        // 각 원소는 자신만으로도 부분 수열을 이룰 수 있기 때문에 최소 길이는 1입니다.
        for (int i = 0; i < N; i++) {
            lds[i] = 1;
        }

        // 동적 계획법을 적용하여 lds 값을 계산합니다.
        // 각 원소 A[i]에 대해 이전 원소 A[j] (j < i)와 비교하여
        // A[j] > A[i]인 경우 lds[i]를 업데이트합니다.
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (A[j] > A[i]) {
                    // A[j] > A[i]이면 lds[i]를 갱신합니다.
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
        }

        // lds 배열에서 가장 큰 값을 찾아서 반환합니다.
        // 이는 가장 긴 감소하는 부분 수열의 길이가 됩니다.
        int maxLDS = 0;
        for (int i = 0; i < N; i++) {
            maxLDS = Math.max(maxLDS, lds[i]);
        }

        return maxLDS;
    }
}

---

질문

1. 동적 계획법을 적용하여 lds 값을 계산 할 경우, 각 for loop의 역할은 무엇일까?
2. 각 원소 A[i]에 대해 이전 원소 A[j] (j < i)와 비교하는 이유는 무엇일까?