공부하기/백준

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

XEV 2023. 11. 16. 23:24

자바 백준 11722번

실버 2

https://www.acmicpc.net/problem/11722

 

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

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 

www.acmicpc.net

 

 

 

 

 

문제 보기

분류: 다이나믹 프로그래밍

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 입력값 받기
        int N = sc.nextInt();
        int[] A = new int[N];
        
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        
        // 가장 긴 감소하는 부분 수열의 길이 구하기
        int maxLength = findLongestDecreasingSubsequenceLength(A);
        System.out.println(maxLength);
    }
    
    // 가장 긴 감소하는 부분 수열의 길이를 찾는 함수
    public static int findLongestDecreasingSubsequenceLength(int[] A) {
        int N = A.length;
        int[] dp = new int[N];
        for (int i = 0; i < N; i++) {
            dp[i] = 1; // 모든 요소를 1로 초기화
        }
        
        // DP 알고리즘을 이용하여 가장 긴 감소하는 부분 수열의 길이 구하기
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (A[j] > A[i]) { // 현재 값이 이전 값보다 작은 경우
                    dp[i] = Math.max(dp[i], dp[j] + 1); // 현재 값의 부분 수열 길이 갱신
                }
            }
        }
        
        // 최대 길이 반환
        int maxLength = 0;
        for (int i = 0; i < N; i++) {
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
    
}