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

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

 

🌘문제 이해하기

• 가장 긴 감소하는 부분 수열 의 길이 구하기 

---

🌗문제 자세히보기 

가장 긴 감소하는 부분 수열 이란 

: 주어진 수열에서 원소의 순서를 유지하면서 값이 점점 작아지는 가장 긴 부분 수열의 길이를 찾는 것 입니다. 

 

예를들어 A의 배열이 있을때 

A = {10,30,20,50,40,30,20} 

 

가능한 감소하는 부분 수열은 아래의 경우와 같습니다. 

• {30,20}
• {50,40}
• {50,40,30}
• {50,40,30,20} 

이 중 가장 긴 수열의 길이는 4입니다. 

• {50,40,30,20} 

이것이 감소하는 부분 수열의 규칙입니다. 

---

🌕최종코드

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException
    {
        int answer = 1;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        ArrayList<Integer> result = new ArrayList<>();

        int n  = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++)
        {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 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);
            }

            answer = Math.max(answer, dp[i]);
        }

        System.out.println(answer);

    }
}