[백준] 11722: 가장 긴 감소하는 부분 수열 - Java (DP)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

가장 긴 증가하는 부분 수열에서는 Bottom-up 방식이 합리적이었다. 그래서 감소하는 부분 수열에서는 반대로 Top-down 방식으로 해서 같은 방식으로 풀어주었다.

 

포인터 i 와 포인터 j 를 가진다. 

둘의 초기값은 arr.length - 1 이다. 그리고 i를 기준으로 하나씩 확인하면서 만약 i 보다 작다면 dp[i] = dp[j] + 1; 을 해준다. 우리는 j를 통해서 반복적으로 확인을 해야하다 보니 Math.max() 로 감싸준다.

 

 

점화식이다.

if(arr[i] > arr[j]){
    dp[i] = Math.max(dp[j] + 1, dp[i]);
}

 

조건문은 코드마다 달라질 수 있겠지만 그 안에 점화식은 큰 변화는 없을 거다.

 

 

 

 

 

 

  풀이

 

 

package src.DP;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 가장긴감소하는부분수열_11722 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];

        // 배열 arr에 입력값을 저장
        for(int i = 1; i <= n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }

        int max = 0;

        for(int i = arr.length - 1; i >= 0; i--){
            for(int j = arr.length - 1; j >= i; j--){

                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }


            }

            max = Math.max(max, dp[i]);
        }

        System.out.println(max);


    }
}