ALGORITHM
[JAVA] 백준 11722번- 가장 긴 감소하는 부분 수열
연듀
2022. 11. 7. 09:47
https://www.acmicpc.net/problem/11722
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int[] dp = new int[n];
dp[0] = 1;
int answer = dp[0];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
for(int i=1; i<n; i++){
int max = 0;
for(int j=i-1; j>=0; j--){
if(arr[i] < arr[j] && dp[j] > max){
max = dp[j];
}
}
dp[i] = max +1;
answer = Math.max(answer, dp[i]);
}
System.out.println(answer);
}
}
이번에는 부분 수열이 감소해야 하므로 arr[i]보다 큰 arr[j]를 찾아야 한다.
반응형