공부 141일차: 백준 11722번 가장 긴 감소하는 부분 수열 자바 java

11722 가장 긴 감소하는 부분 수열

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

11722번: 가장 긴 감소하는 부분 수열

 

 

 

 

---

백준 11722번 문제 가장 긴 감소하는 부분 수열

---

문제

---

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/249

공부 128일차: 백준 11053번 가장 긴 증가하는 부분 수열 자바 java

 

위와 비슷한 문제다

대신 감소하는 수열이므로 LIS 대신 LDS(Longest Decreasing Sequence)를 구한다

 

arr	10	30	10	20	20	10
dp	1	1	2	2	2	3

가장 작은 수열의 크기는 자기 자신만을 수열로 가지는 경우이므로 1로 dp[]값을 모두 초기화한다

 

이후 주어진 표처럼 원하는 숫자에서 거꾸로 가면서,

그 arr[n]의 값보다 큰 값이 있다면 dp[n](1)과 그 해당 수 i의 dp[i]에 1을 더하는 것을 비교하는 것이다

 

즉, 20일 때 앞에 자신보다 큰 30이 있으므로 1과 1+1 중 비교하고

마지막 10일 때 앞에 자신보다 큰 20이 있으므로 1과 2+1 중 비교하는 식이다 (이후 30이라는 자신보다 큰 숫자를 만나지만 1+1과 3 중 3이 더 크므로 그대로 유지한다)

 

int LIS(int n) {
    if(dp[n] == 0) {
        dp[n] = 1;
            
        for(int i = n-1; i >= 0; i--) {
            if(arr[i] < arr[n]) {
                dp[n] = Math.max(dp[n], LIS(i)+1);
            }                
        }
    }
    return dp[n];
}

LIS에서 if절의 부등호 방향만 바꿔주면 LDS를 구할 수 있다

int LDS(int n) {
    if(dp[n] == 0) {
        dp[n] = 1;
            
        for(int i = n-1; i >= 0; i--) {
            if(arr[i] > arr[n]) {
                dp[n] = Math.max(dp[n], LDS(i)+1);
            }                
        }
    }
    return dp[n];
}

 

 

 

---

정답 인정 코드

---

 

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[] arr;
    static int[] dp;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        dp = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            LDS(i);    // arr[i]값을 넣으면서 dp[i]값도 구한다
        }
        // 디버깅
//        System.out.println(Arrays.toString(arr));
//        System.out.println(Arrays.toString(dp));
        
        int max = 0;    // dp[n]은 무조건 1 이상이므로
        for(int i = 0; i < n; i++) {
            max = Math.max(max, dp[i]);
        }
        
        System.out.println(max);
    }
    
    static int LDS(int n) {
        if(dp[n] == 0) {
            dp[n] = 1;
            
            for(int i = n-1; i >= 0; i--) {
                if(arr[i] > arr[n]) {    //이전에 자신보다 큰값이 있다면
                    dp[n] = Math.max(dp[n], LDS(i)+1);
                }                
            }
        }
        return dp[n];
    }
 
}
 

설명했듯, LIS에서 if절의 부등호 방향만 바꿔주면 LDS를 구할 수 있다

 

 

 

---

굉장히 유사한 문제가 있기도 하고, LDS는 필수적인 개념이다 보니 정답률이 높은 것 같다

어렵지 않은 것도 사실이고..