99클럽 코테 스터디 27일차 TIL DP(가장 긴 감소하는 부분 수열)

 

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

 

<아이디어>

1시간 동안 고민했는데 도오저히 아이디어가 안 떠올라서 힌트를 봤다 >.<

순서대로 탐색하면서 현재 값보다 이전 값의 크기를 비교하며 수열의 길이를 메모이제이션 하면 된다.

현재 값보다 이전 값이 클 때 그 이전 값에 + 1을 수열의 크기로 저장하면서 갱신해주면 된다.

자세히 분석해보면 아래와 같다.

10 30 10 20 20 10
10 : dp[0] = 1
10, 30 => 10 or 30 : dp[1] = 1
10, 30, 10 => 30, 10 : dp[2] = dp[1] + 1
10, 30, 10, 20 => 30, 20 : dp[3] = dp[1] + 1
10, 30, 10, 20, 20 => 30, 20 : dp[4] = dp[1] + 1
10, 30, 10, 20, 20, 10 => 30, 20, 10 : dp[5] = Math.max(dp[1] + 1, dp[3] + 1, dp[4] + 1)

휴 디피 어렵다... 이번주안에 디피 뿌셔야지

 

<제출코드>

package Study.Week04;

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

public class Day27_BOJ_11722_가장긴감소하는부분수열 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int ans = 1;
        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                // 이전에 현재보다 큰 값이 있으면
                if(arr[j] > arr[i]) dp[i] = Math.max(dp[i], dp[j]+1);
            }
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }
}