문제

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

풀이

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

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

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

        for(int i = 2; i <= N; i++) {
            for(int j = 1; j < i; j++) {
                if(num[j] > num[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }

        Arrays.sort(dp);
        System.out.println(dp[N]);
    }
}

접근 방법

1. 정수형 배열 dp에 저장되는 값은, 감소하는 형태의 불연속 수열에서 해당 원소의 순서이다.

후기

점점 큰 값으로 갱신해가는 형태의 dp 문제처럼 접근하여 오랜 시간이 걸렸다. 각 원소마다 비교하는 형태도 있으니 기억해 두어야겠다.