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

2025. 6. 30. 13:04·Algorithm & Data Structures/BOJ

 

 

 

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

 


 

📌 문제 개요

 

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

 

  • 예를 들어, 수열이 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);
    }
}

'Algorithm & Data Structures > BOJ' 카테고리의 다른 글

b2225. 합분해  (0) 2025.06.30
b1699. 제곱수의 합  (0) 2025.06.30
b11055. 가장 큰 증가하는 부분수열  (0) 2025.06.23
b11057. 오르막수  (0) 2025.06.23
b6497. 전력난  (0) 2025.06.23
'Algorithm & Data Structures/BOJ' 카테고리의 다른 글
  • b2225. 합분해
  • b1699. 제곱수의 합
  • b11055. 가장 큰 증가하는 부분수열
  • b11057. 오르막수
Geisha
Geisha
개발 일기
  • Geisha
    Geisha
    Geisha
  • 전체
    오늘
    어제
    • 분류 전체보기 (335)
      • Algorithm & Data Structures (253)
        • BOJ (111)
        • SWEA (1)
        • Programers (137)
        • Data Structures (3)
      • DB (29)
        • SQL (23)
        • RDBMS (2)
      • Java (1)
        • Class (1)
      • Spring (5)
        • Spring MVC (1)
        • Annotations (1)
      • CS (36)
        • 운영체제 (13)
        • 네트워크 (5)
      • Tool (6)
        • Git (5)
        • AWS (1)
      • Project (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    SQL
    유니온파인드
    전위순회
    프로그래머스
    다익스트라
    BFS
    PriorityQueue
    구현
    백준
    자바
    Stack
    이분탐색
    baekjoon
    투포인터
    백트래킹
    후위순회
    Dijkstra
    동적계획법
    Union-Find
    경로압축
    programmers
    알고리즘
    binarySearch
    DynamicProgramming
    Java
    algorithm
    dp
    골드
    스택
    dfs
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
Geisha
b11722. 가장 긴 감소하는 부분수열
상단으로

티스토리툴바