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

문제

예제

풀이

이전에 풀었던 문제 - [PS] 백준 11053번 가장 긴 증가하는 부분 수열 - DP 를 조금만 바꾸면 된다.'

코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt(); //수열의 크기

        int[] arr = new int[n+1];//값
        int[] dp = new int[n+1];//dp[탐색길이]에 가장 긴 수열의 길이 저장

        for(int i=1; i<=n; i++) { //수열입력받기
            arr[i] = in.nextInt();
        }

        dp[1] = 1;
        int max = 1;

        for(int i=2; i<=n; i++) {
            dp[i] = 1;

            for(int j=1; j<i; j++) {//1부터 현재위치까지 탐색

                //dp를 arr[1]부터 비교하면서 초기화
                if(arr[j] > arr[i] && dp[j] >= dp[i]) {
                    dp[i] = dp[j] +1; //길이 +1 누적
                }
            }
            max = Math.max(max,dp[i]); //최대값과 비교
        }

        System.out.println(max);

    }
}