[Java] 11722. 가장 긴 감소하는 부분 수열

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

 

문제 접근 과정

 

• 주어진 배열에서 각 원소를 마지막 원소로 하는 최장 증가 부분 수열의 길이를 저장하는 dp 배열을 사용
• 점화식:
  • dp[i] = max(dp[j] + 1) (단, j < i이고 array[j] < array[i]일 때)
• 최종적으로 dp 배열에서 최댓값을 찾으면 가장 긴 증가하는 부분 수열의 길이를 구할 수 있습니다.

 

코드

import java.io.*;
import java.util.*;

public class Main {    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] array = new int[n];
		int[] dp = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < n; i++) {
			array[i] = Integer.parseInt(st.nextToken());
			dp[i] = 1;
		}
		
		int maxLength = 1;
		
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (array[j] > array[i]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			maxLength = Math.max(maxLength, dp[i]);
		}
		
		System.out.println(maxLength);
	}
}