b11722. 가장 긴 감소하는 부분수열

 

 

 

✨ 자바로 푸는 가장 긴 감소하는 부분 수열 문제 풀이

 

---

 

📌 문제 개요

 

수열이 하나 주어졌을 때, 해당 수열에서 가장 긴 감소하는 부분 수열의 길이를 구하는 문제입니다.

 

• 예를 들어, 수열이 10 30 10 20 20 10이라면
• 가장 긴 감소하는 부분 수열은 30 20 10 → 길이 3

 

👉 이 문제는 **Longest Decreasing Subsequence (LDS)**를 찾는 전형적인 DP 문제입니다.

 

---

 

💡 예제 입력

6  
10 30 10 20 20 10

 

💡 예제 출력

3

 

---

 

🛠 알고리즘 접근 방식

 

**가장 긴 증가하는 부분 수열(LIS)**과 동일한 접근 방식이며,

조건만 arr[j] > arr[i]로 바뀝니다.

 

 

🔸 DP 정의

 

• dp[i]: i번째 원소를 마지막으로 하는 가장 긴 감소 수열의 길이

 

 

🔸 점화식

 

• arr[j] > arr[i]를 만족하면
• dp[i] = max(dp[i], dp[j] + 1)

 

---

 

✅ 핵심 아이디어

 

• 각 위치마다, 이전 수 중 나보다 큰 수만 선택 가능
• 선택한 수열이 감소해야 하므로 arr[j] > arr[i] 조건
• 현재 위치에서 만들 수 있는 최장 수열을 계속 갱신

 

---

 

🧾 코드 해설

int[] dp = new int[N];
Arrays.fill(dp, 1); // 자기 자신만 있을 경우 길이 1

for (int i = 0; i < N; i++) {
    for (int j = 0; j < i; j++) {
        if (arr[j] > arr[i]) { // 감소 조건
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

 

• 마지막에 dp 배열에서 가장 큰 값이 정답입니다.

int answer = 0;
for (int i = 0; i < N; i++) {
    answer = Math.max(answer, dp[i]);
}

 

---

 

✅ 핵심 포인트 정리

 

• dp[i]: i번째를 마지막으로 하는 감소 수열 길이
• arr[j] > arr[i] 조건으로 감소 수열 유지
• LIS와 거의 동일한 구조 → 조건만 반대로

 

 

 

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

public class Main {

    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] dp = new int[N];
        Arrays.fill(dp, 1);

        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < i ; j++){
                if(arr[j] > arr[i]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }

        int answer = 0;
        for(int i = 0 ; i < N ; i++){
            answer = Math.max(answer, dp[i]);
        }
        System.out.println(answer);
    }
}