0%

[백준/11054] 가장 긴 바이토닉 부분 수열

작성일 Edited on In Disqus:

Baekjoon Online Judge - 11054

Review

이 문제는 가장 긴 증가하는 부분 수열(LIS)을 두 번 활용하면 되는 문제이다.

result
이렇게 오른쪽, 왼쪽 방향으로 진행하는 LIS의 길이를 구해 각 배열에 저장한 다음, 그 두 배열의 값이 최대가 되는 지점이 바로 정답이 된다.

result
오른쪽으로 진행하는 LIS의 값은 DP 배열에 저장하고, 왼쪽으로 진행하는 LIS의 값은 R 배열에 저장한다. 따라서 아까 말했듯이, DP[i]+R[i]로 나온 값들 중의 최대값이 바로 정답이 되는 것이다.

그런데 왜 정답은 7인데 더한 값은 8일까? 바로 가운데 값이 중복되기 때문에 그렇다.

  • DP배열의 LIS: 1, 2, 3, 4, 5
  • R배열의 LIS: 1, 2, 5
  • 총 길이: 1, 2, 3, 4, 5, 5, 2, 1

이렇게 5가 중복이 되기 때문에 1을 빼줘야 정답이 된다.

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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[] R = new int[N + 1];
    int ans1 = 1;
    int ans2 = 1;
    int max = 0;
    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);
        }
      }
      ans1 = Math.max(ans1, DP[i]);
    }

    // 왼쪽으로 진행
    for(int i = N; i >= 1; i--) {
      R[i] = 1;
      for(int j = N; j >= i; j--) {
        if(A[i] > A[j]) {
          R[i] = Math.max(R[i], R[j] + 1);
        }
      }
      ans2 = Math.max(ans2, R[i]);
    }

    // 최대값 구하기
    for(int i = 1; i <= N; i++) {
      max = Math.max(DP[i] + R[i], max);
    }

    // 1을 뺀 결과값
    System.out.println(max-1);

  }

}