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

dp와 또 멀어지기 ~
어렵지만 꾸준히 오래오래!

나는 어리석게도 값을 순차적으로 돌면서 현재값이 이전값보다 크면 카운트를 올리고 그 카운트가 가장 큰 걸 리턴해주는 .. 결국은 테스트 케이스만 통과하고 엉터리인 접근을 했다. 오래 잡고 있는다고 해결되는 게 아니므로 빠르게 풀이 흡수!

package baekjoon;

import java.util.Arrays;
import java.util.Scanner;

public class Main_11053 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();   // 수열 A의 크기
        int[] A = new int[N];
        int[] dp = new int[N];

        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        for (int i = 0; i < N; i++) {
            dp[i] = 1;

            for (int j = 0; j < i; j++) {
                if(A[j] < A[i] && dp[i] < dp[j]+1) {
                    dp[i] = dp[j]+1;
                }
            }
        }

        System.out.println(Arrays.stream(dp).max().getAsInt());
        /*
        * OptionalInt[4] -> getAsInt로 값을 꺼내줌
        * intStream과 같은 기본 스트림은 Optional도 기본형을 값으로 하는 OptionalInt, OptionalLong, OptionalDouble을 반환한다
        * */
    }
}

나는 재귀를 쓰는 top-down 방식보단 bottom-up 방식이 좀 더 생각해내기가 덜 어렵다..
현재 값을 기준으로 이전 원소들의 값을 탐색해서 최대값을 구한다. 아직 완벽히 내것으로 만들지 못한 것 같아서 재귀탐색 방식까지 이해하고 풀이를 다시 적어야겠다 ..