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

DP 유형은 많이 안풀어봐서 그런가 잘 모르겠다.. 30분 이상 고민하지 말고 모르겠으면 풀이보라길래 결국 풀이보고 제출 성공 ㅠ
많이 푸는게 답이라고 했으니 많이 풀어봐야지

package baekjoon;

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

import static java.lang.Math.max;

public class Main_11722 {
    static int N = 0;
    static int[] dp;
    static int[] array;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.valueOf(br.readLine());     // 수열의 크기
        array = new int[N];
        dp = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int i = 0;
        while (st.hasMoreTokens()) {
            int a = Integer.valueOf(st.nextToken());
            array[i] = a;
            i++;
        }
        dp();
    }
    public static void dp() {
        int max = 1;
        for (int i = 0; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if(array[j] > array[i] && dp[j]+1 > dp[i]) {
                    dp[i] = dp[j]+1;
                    max = max(max, dp[i]);
                }
            }
        }
        System.out.println(max);
    }
}

🙋‍♀️ 아직도 완벽하게 이해는 되지 않지만 DP는 기억하며 프로그래밍하는 방법이다. 반복되는 동작 속에서 해당 위치까지의 값을 기억하는게 중요한 키포인트 같다.
풀이는 (내껀 아니지만)
0번 인덱스부터 마지막 6번 인덱스까지 각자 인덱스가 가질 수 있는 최댓값을 기억하여 최종적으로 가장 큰 값을 리턴해주면 된다.
문제를 예로 들면
A = {10 30 10 20 20 10}
0번 인덱스에서 가질 수 있는 최댓값 : 1
- {10}
- 비교군이 없으므로 기본값 1
1번 인덱스에서 가질 수 있는 최댓값 : 1
- {10, 30}
- 현재 인덱스보다 직전 인덱스가 작으므로 (10 < 30) 기본값 1
2번 인덱스에서 가질 수 있는 최댓값 : 2
- {10, 30, 10}
- 현재 인덱스 10이 직전 인덱스 30보다 작고 현재 인덱스를 선택했을 때 최댓값이 갱신가능하므로 +1
3번 인덱스에서 가질 수 있는 최댓값 : 2
- {10, 30, 10, 20}
- 현재 인덱스 20이 전전 인덱스 30보다 작으므로 +1
- 하지만 현재 인덱스를 선택했을 때 직전까지 선택했을 때 가질 수 있는 최댓값보다 크지 않으므로 넘어감
4번 인덱스에서 가질 수 있는 최댓값 : 2
- {10, 30, 10, 20, 20}
- 위와 같은 이유로 2에서 그침 (20 < 30) +1
5번 인덱스에서 가질 수 있는 최댓값 : 3
- {10, 30, 10, 20, 20, 10}
- 현재 인덱스 10이 30보다 작고 +1 20보다 작음 +1

글로 적으니 조금 어려운 것 같기도 하고.. 난 실제로 코드 이해하기도 좀 어려웠던 것 같기도 하고.. dp[j]+1 > dp[i] 이 부분이 좀 난해하했는데 (나는..) 현재 인덱스를 선택했을 때 값이 더 큰 지 아니면 그직전 인덱스까지 선택했을 때 가지고 있던 값이 더 큰 지를 생각해보면 될 것 같다.
결국 가장 긴 감소하는 수열의 길이는 3이 된다.