0%

[백준/11722] 가장 긴 감소하는 부분 수열

작성일 Edited on In Disqus:

Baekjoon Online Judge - 11722

Review

  • 백준 11053 문제를 풀었다면, 부등호 하나만 고쳐서 풀 수 있는 문제이다.
  • 그래서 그런지 정답률이 꽤 높다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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 bf = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bf.readLine());
    int[] A = new int[N + 1];
    int[] DP = new int[N + 1];
    int ans = 1;
    StringTokenizer st = new StringTokenizer(bf.readLine());
    
    for(int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    
    for(int i = 1; i <= N; i++ ) {
      DP[i] = 1;
      for(int j = 1; j <= i; j++) {
        if(A[i] < A[j]) {
          DP[i] = Math.max(DP[i], DP[j] + 1);
        }
      }
      ans = Math.max(ans, DP[i]);
    }
    
    System.out.println(ans);
    
  }
  
}