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

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr, dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N];    // LDS = LIS를 오른쪽에서 수행한 거
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }
        
        int result = 0;    
        for(int i = N - 1 ; i >= 0 ; i--) {     // 🔔 뒤에서부터 시작 🔔
            for(int j = N - 1 ; j > i ; j--) {  // 🔔 맨 뒤에서 i 이전 원소들 탐색 🔔
                if(arr[j] < arr[i]) { // 감소하는 수열
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            
            result = Math.max(result, dp[i]);
        }
        
        System.out.println(result);
    }
}
 

✅ 해결 아이디어
✔ LDS
- LIS를 오른쪽에서부터 수행

 

💥 유의사항

• 감소하는 부분 수열 LDS의 길이 ⇨ 뒤에서부터 증가하는 부분 수열의 길이 구하는 것과 같음

 

 

---

🔺 다른 풀이들

- 정방향으로 (왼 →오) 수행하심 (이전 값이 크다면 = 감소하는 수열 = if arr[j] > arr[i])

 → dp : 각 원소당 가장 긴 감소 부분 수열

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

[백준] S2 11722번 가장 긴 감소하는 부분 수열 (JAVA)

 

 

- binarySearch를 활용한 풀이 (시간 복잡도 : O(n log n)

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

---

💬 느낀 점

LIS를 제대로 이해해야 LDS도 잘 해낼 수 있는 거 같다...!

 

그냥 부등호 방향만 바꾸면 되는데 뒤에서부터 구해버리기...ㅎ

 

1회독	2회독	3회독	4회독	5회독
V	8.3

 

 

(+ 8.3 2회독)

이진 탐색 활용 (시간 복잡도 ; O(N logN))

알고리즘 풀이 - 백준 11722(가장 긴 감소하는 부분 수열, DP)

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

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] A, LIS;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        LIS = new int[N];
        LIS[0] = A[0];
        int end = 0;
        
        for(int i = 1 ; i < N ; i++) {
            // 원 배열 탐색 중 더 작은 숫자라면 그대로 이어붙임
            if(LIS[end] > A[i]) {
                LIS[++end] = A[i];
            }
            else {
                int targetIdx = binarySearch(end, i);
                LIS[targetIdx] = A[i];
            }
        }
        
        System.out.println(end + 1);
    }
    
    private static int binarySearch(int end, int idx) {
        int start = 0;
        
        while(start <= end) {
            int mid = (start + end) / 2;
            
            if(LIS[mid] == A[idx])       return mid;
            else if(LIS[mid] > A[idx])   start = mid + 1;
            else if(LIS[mid] < A[idx])   end = mid - 1;
        }
        
        return start;   // 일치값 찾지 못 했을 때, 적절한 위치 반환
    }
}

---

(참고)

[백준/JAVA] 11054번: 가장 긴 바이토닉 부분 수열