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

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

---

 

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

 

위 문제와 매우 유사한 문제이다.

이번에도 dp에 해당 숫자로 만들수 있는 감소하는 수열 길이를 저장하였고

위 문제와 다른점이 있다면 1 부터 N까지 수열이 아닌

N부터 1까지 증가하는 수열을 구하여 감소하는 수를 구했다.

( N부터 1까지 증가하는 수열은 1부터 N까지 감소하는 수열이기때문에 )

 

i 는 Arr[ N ] =1 이고 Arr[ N-1 ] 부터 해당 DP를 구하게된다.

DP[ 3 ] 을 구하기 위해서는 DP[ 6 ] , [ 5 ] , [ 4 ] 와 비교를 하게 된다.

 

비교 조건은 아래와 같다

( i 는 현재 index, j 는 비교하는 index )

1. Arr [ i ] 는 Arr [ j ] 보다 커야하고
2. dp[ i ] 는 dp [ j ] 보다 작거나 같아야한다.
3.  

이런식으로 각각의 DP를 구한 후 해당 DP배열 중 가장 긴(큰) 값을 출력하면 된다.

 

---

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

public class B11722 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] board  = new int[N+1];
        int[] dp = new int[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }

        dp[N] = 1;
        int res = 1;
        for (int i = N-1; i >= 1; --i) {
            dp[i] = 1;
            for (int j = N; j > i; --j) {
                if(board[i] > board[j] && dp[i] <= dp[j]){
                    dp[i] += 1;
                }
            }
            res = Math.max(res , dp[i]);
        }
        System.out.println(res);
        br.close();
    }
}