99클럽 코테 스터디 32일차 TIL (미들러): [백준][Java] 11054 가장 긴 바이토닉 부분 수열 - 골드4

 

문제 보기

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

 

 

풀이

증가하는 가장 긴 수열과 감소하는 가장 긴 수열의 합체 버전이라 생각했다.

0번부터 N-1까지 DP를 돌리며 해당 인덱스를 마지막으로 하는 가장 긴 증가 수열을 찾아내고,

N-1번부터 0번까지 DP를 돌리며 해당 인덱스를 처음으로 하는 가장 긴 감소 수열을 찾아냈다.

 

그리고 0부터 N-1까지 순회를 돌리며 증가 수열 DP + 감소 수열 DP - 1(자기 자신이 중복되기 때문)을 한다.

현재 인덱스를 반환 점으로 생각하는 것이다.

그러면 가장 긴 바이토닉 부분 수열을 찾아낼 수 있게 된다!

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    int[] arr = new int[N];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    int[] dpUp = new int[N];
    int[] dpDown = new int[N];
    for (int i = 0; i < N; i++) {
      dpUp[i] = 1;
      for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
          dpUp[i] = Math.max(dpUp[i], dpUp[j] + 1);
        }
      }
    }

    for (int i = N - 1; i >= 0; i--) {
      dpDown[i] = 1;
      for (int j = N - 1; j > i; j--) {
        if (arr[j] < arr[i]) {
          dpDown[i] = Math.max(dpDown[i], dpDown[j] + 1);
        }
      }
    }

    int max = 0;
    for(int i = 0; i < N; i++) {
      max = Math.max(max, dpUp[i] + dpDown[i] - 1);
    }

    bw.write(max + "");
    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/11054.%E2%80%85%EA%B0%80%EC%9E%A5%E2%80%85%EA%B8%B4%E2%80%85%EB%B0%94%EC%9D%B4%ED%86%A0%EB%8B%89%E2%80%85%EB%B6%80%EB%B6%84%E2%80%85%EC%88%98%EC%97%B4

CodingTest_AutoSave/백준/Gold/11054. 가장 긴 바이토닉 부분 수열 at main · MetroDefro/CodingTest_AutoSave