[백준] 가장 긴 증가하는 부분 수열 - 11053번

가장 긴 증가하는 부분 수열

1 초	256 MB	169140	67958	45098	38.082%

문제

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

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

입력

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

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

출력

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

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)을 동적 프로그래밍(DP)을 이용하여 해결하는 Java 코드를 작성해드리겠습니다. 이 문제는 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 문제입니다. DP를 사용하면 효율적으로 해결할 수 있습니다.

Java 코드

import java.util.Scanner;

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

        // 수열 A의 크기 N 입력
        int N = scanner.nextInt();
        int[] A = new int[N];

        // 수열 A의 요소들 입력
        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }

        // DP 배열 초기화
        int[] dp = new int[N];
        int maxLength = 1;  // LIS의 최소 길이는 1

        // DP 초기값 설정
        for (int i = 0; i < N; i++) {
            dp[i] = 1;
        }

        // DP를 이용하여 LIS 계산
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] > A[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
            // 현재까지의 최대 LIS 길이 업데이트
            if (maxLength < dp[i]) {
                maxLength = dp[i];
            }
        }

        // 결과 출력
        System.out.println(maxLength);

        scanner.close();
    }
}

코드 설명

1.입력 처리:

• 첫째 줄에서 수열의 크기 ( N )을 입력받고, 두 번째 줄에서 수열 ( A )의 요소들을 입력받습니다.

2.DP 배열 초기화:

• dp 배열은 각 인덱스까지의 가장 긴 증가하는 부분 수열의 길이를 저장합니다. 초기값으로 모든 dp 값을 1로 설정합니다. 이는 각 요소 자체만으로도 길이 1의 증가하는 부분 수열이 되기 때문입니다.

3.DP 계산:

• 이중 루프를 사용하여 dp 배열을 업데이트합니다.
• A[i]가 A[j]보다 크고(A[i] > A[j]), dp[i]가 dp[j] + 1보다 작다면 dp[i]를 dp[j] + 1로 업데이트합니다.
• 이는 A[j]까지의 부분 수열에 A[i]를 추가하여 새로운 증가하는 부분 수열을 만들 수 있기 때문입니다.

4.최대 길이 계산:

• 각 dp[i] 값을 비교하여 현재까지의 가장 긴 증가하는 부분 수열의 길이를 maxLength로 업데이트합니다.

5.결과 출력:

• maxLength를 출력하여 가장 긴 증가하는 부분 수열의 길이를 결과로 나타냅니다.

이 코드는 시간 복잡도 ( O(N^2) )로, 입력 크기 ( N )이 1,000 이하일 때 효율적으로 동작합니다.