풀이 방법
각 원소들마다 양쪽을 기준으로 최장 부분 수열을 개수를 구해주었다.
각 dp에 저장된 값을 이용해서 바이토닉 부분 수열을 구할 수 있다.
내 코드
package com.company;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] arr, dp1, dp2;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
arr = new int[N + 2];
dp1 = new int[N + 2];
dp2 = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= N; i++) {
for (int j = i - 1; j >= 0; j--) {
if (arr[i] > arr[j]) {
dp1[i] = Math.max(dp1[i], dp1[j] + 1);
}
}
}
for (int i = N; i > 0; i--) {
for (int j = i + 1; j <= N + 1; j++) {
if (arr[i] > arr[j]) {
dp2[i] = Math.max(dp2[i], dp2[j] + 1);
}
}
}
int answer = 0;
for (int i = 1; i <= N; i++) {
answer = Math.max(dp2[i] + dp1[i] - 1, answer);
}
System.out.println(answer);
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
플로이드 2 - 11780번 (0) | 2022.02.08 |
---|---|
최소 회의실 개수 - 19598번 (0) | 2022.02.07 |
스타트택시 - 19238번 (0) | 2022.02.07 |
소수상수근 - 9421번 (0) | 2022.02.07 |
스카이라인 쉬운거 - 1863번 (0) | 2022.02.04 |