백준 11053번 가장 긴 증가하는 부분순열

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

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

풀이방법

📢 arr[n]에 들어있는 수보다 이전에 더 작은 값의 길이가 dp배열에 담기게 된다.
이때 arr[n]보다 작은 arr[i]값들중 dp배열의 값중에 최대값+1로 현재 dp배열에 저장한다.

주의할 점은 최소길이가 1이므로, 전부 1로 초기화 해줘야 한다는 점이다.
또한 recur(N)한번이 dp[6]을 구하는 방법이기 때문에, 모든 dp배열이 채워 지는 것이 아니다.
따라서 각 요소들을 전부 recur(i) 해줘서 dp배열을 구한뒤,
dp배열의 최대값을 찾아준다.

후기

하,, 진짜 개 어렵다