[백준] 11722 가장 긴 감소하는 부분 수열 자바 풀이 DP

[백준] 11722 가장 긴 감소하는 부분 수열 자바 풀이 DP

 

 

본 문제에선 숫자가 감소하지만 반대로 생각하면 증가이기 때문에 LIS문제입니다

최장 증가 부분수열 (LIS, Longest Increasing Subsequence).

 

 

저번에 풀었던 LCS도 참고하시면 좋을 것 같습니다

2024.08.22 - [알고리즘 단련장/백준] - [백준] 9251 LCS 최장 공통 부분수열 자바 풀이 DP

[백준] 9251 LCS 최장 공통 부분수열 자바 풀이 DP

 

 

 

 

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

 

 

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 30 10 20 20 10

예제 출력 1 복사

3

출처

• 문제를 만든 사람: baekjoon

비슷한 문제

• 11053번. 가장 긴 증가하는 부분 수열
• 11054번. 가장 긴 바이토닉 부분 수열
• 11055번. 가장 큰 증가하는 부분 수열
• 12015번. 가장 긴 증가하는 부분 수열 2
• 12738번. 가장 긴 증가하는 부분 수열 3
• 14002번. 가장 긴 증가하는 부분 수열 4
• 14003번. 가장 긴 증가하는 부분 수열 5

알고리즘 분류

• 다이나믹 프로그래밍

 

 핵심 설명

 

dp[i] = i번째 숫자를 기준으로

내 왼쪽을 봤을때

"연속된 감소하는 수"의

최대 길이는?

을 의미합니다

 

ex.

10 30 10 20

에서 dp[3] = 20을 기준으로

30 20 이 있기 때문에

2입니다

 

이걸 코드로 구현하면 다음과 같습니다

// dp[i] = "i번째 숫자를 기준으로, 왼쪽에 나보다 큰 연속된 수, 최대 몇개냐?"

        for(int i=2;i<=n;i++) {         // 기준값
            for(int j=1;j<=i-1;j++) {     // 이전값들
                if(arr[j] > arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
                // System.out.print(dp[i] + " ");
            }
            // System.out.println();
            max = Math.max(max, dp[i]);
        }

 

 

전체 코드

import java.io.*;
import java.sql.SQLOutput;
import java.util.*;

public class Main {

    public static long dap = 0;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

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



        int dp[] = new int[n+1];
        Arrays.fill(dp, 1);
        int max = 1;

        // dp[i] = "i번째 숫자를 기준으로, 왼쪽에 나보다 큰 연속된 수, 최대 몇개냐?"
        //   10 30 10 20 80 10
        //    1  1  2  2  2  3
        // 두번째인 30부터 돌면서 왼쪽에 한놈 체크해보자
        // (10) > 30 인지 체크, dp[i] 계속 유지
        // 세번째인 10 체크해볼껀데 왼쪽에 두놈 있네?
        // (10, 30) > 10, 한번은 유지했다가, 30>10 만났을때 +1되서 2되겠네
        // 네번째인 20 체크해볼껀데 왼쪽에 세놈있네?
        // (10, 30, 10) > 20, 30>20 만났을때 +1되서 2 되겠네
        // (다섯번째 스킵)
        // 여섯번째 10 체크해볼껀데, 왼쪽에 다섯놈있네?
        // (10, 30, 10, 20, 80) > 10, 30>10 만났을때 2되고, 20>10 만났을때 3되겠네
        for(int i=2;i<=n;i++) {         // 기준값
            for(int j=1;j<=i-1;j++) {     // 이전값들
                if(arr[j] > arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
                // System.out.print(dp[i] + " ");
            }
            // System.out.println();
            max = Math.max(max, dp[i]);
        }

        for(int i=1; i<=n; i++) {
            // System.out.println("dp[i] = " + i + " " + dp[i]);
        }

        dap = max;

        bw.write(String.valueOf(dap) + "\n");
        bw.flush();
        bw.close();
        return;
    }
}