바로 전에 풀었던 가장 긴 감소하는 부분 수열의 길이와 전체적인 흐름은 같다.
나보다 이전에 나왔던 숫자들 중에 더 작은 숫자가 있다면,
그 숫자부터 자신까지를 포함하는 수열의 길이가 더 긴지 비교하고 값을 갱신해주면 된다.
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
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+1];
int[] dp = new int[N+1];
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int i=1;i<=N;i++){
arr[i] = Integer.parseInt(st.nextToken());
}
dp[1] = 1;
for(int i=2;i<=N;i++){
dp[i] = 1;
for(int j=0;j<i;j++){
if(arr[i]>arr[j]&&dp[i]<=dp[j]+1) dp[i] = dp[j]+1;
}
}
int max = 0;
for(int val : dp) if(val>max) max = val;
System.out.println(max);
}
}
'[BOJ] - JAVA' 카테고리의 다른 글
[백준] 11004 : K번째 수 JAVA 풀이 (0) | 2022.06.11 |
---|---|
[백준] 11057 : 오르막 수 JAVA 풀이 (0) | 2022.06.10 |
[백준] 11722 : 가장 긴 감소하는 부분 수열 JAVA 풀이 (0) | 2022.06.08 |
[백준] 11726 : 2xn 타일링 JAVA 풀이 (0) | 2022.06.08 |
[백준] 2579 : 계단 오르기 JAVA 풀이 (0) | 2022.06.08 |