(Java) 백준 11722번 - 가장 긴 감소하는 부분 수열

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

문제

> 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

> 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 
가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

접근

수열 A의 모든 수에 대해 dp는 각 수열의 수를 마지막으로 가지는 감소하는 부분 수열의 길이를 말한다.
따라서 기본적으로 자기 자신을 가지므로 dp의 기본값은 1로 설정한다.
문제를 만족하기 위해선 내 앞에 있는 수들중 나보다 큰 수들이 있어야 나의 dp값이 커지게 된다. 따라서 dp(i)값을 위해서 0부터 i번째까지 중 i보다 큰 수가 있는지 확인하며 있다면 그 수(J라고하자) dp(j)값에 i번째 수를 마지막으로 이어붙일 수 있다. 그래서 dp(i)는 dp(j)+1이 된다. 근데 나보다 큰 수가 어러개가 있을 수 있으므로
dp(j)+1과, dp(k)+1, dp(t)+1 등등 중 가장 큰 수를 dp(i)로 가지면 된다.

문제해결

> 수열의 원소 수 N을 입력받고 num배열에 수열을 입력받는다.
> 부분수열의 길이를 저장할 dp를 N크기로 선언하고 초기값을 1로 초기화 해준다.
> 수열의 0번쨰 수 부터 차례대로 dp 즉, 부분수열을 구해준다.
> 감소하는 부분수열이므로 j를 통해 0부터 i번째까지 매번 순회하며 나보다 큰 수가 앞에 있나 본다.
> 있다면 해당 수의 dp값+1(i번째를 이어붙인 수) 와, 현재 i번째에 저장된 dp값을 최대값 연산해 더 큰 수로 갱신한다.
> 모든 수의 dp를 구했으면 모든 수 중 어떤 수로 끝났을 때가 가장 긴 수열인지 확인해야한다.
> dp값을 전부 돌며 가장 큰 수를 반환한다.

코드

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

public class Main {
    //11722번 가장 긴 감소하는 부분 수열
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int[] num = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) num[i] = Integer.parseInt(st.nextToken());
        int[] dp = new int[N];
        Arrays.fill(dp, 1);

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < i; j++) {
                if(num[j] > num[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int rst = 0;
        for(int i : dp) rst = Math.max(rst, i);
        System.out.print(rst);
    }
}

후기

예전에 풀었던거라 어떻게 푸는지 기억이 나지않아 고민 많이 했다. 그래도 했던거라 이거 어떻게 했었는데? 라는 희미한 기억이 있어서 풀렸다.