가장 긴 바이토닉 부분 수열
10
ARR : 1 5 2 1 4 3 4 5 2 1
LIS : 1 2 2 1 3 3 4 5 2 1
LDS : 1 5 2 1 4 3 3 3 2 1
DP = LIS[i] + LDS[i] - 1
DP : 1 6 4 1 6 5 6 7 3 1
LIS값을 나타내는 부분수열.
{1} , 1
{1,5}, 2
{1,2}, 2
{1}, 1
{1,2,4} , 3
{1,2,3} , 3
{1,2,3,4}, 4
{1,2,3,4,5}, 5
{1,2} 2
{1}, 1
LDS를 나타내는 부분 수열.
{1}, 1
{5,4,3,2,1}, 5
{2,1}, 2
{1}, 1
{4,3,2,1}, 4
{3,2,1}, 3
{4,2,1}, 3
{5,2,1}, 3
{2,1}, 2
{1}, 1
LDS + LIS 합해보면 아래와 같이 절묘하게 하나의 중복요소가 존재하는 배열의 길이가 된다.
예를 들어 생각을 해보면....
ex)
{5,4,3,2,1},5 {1,5}, 2
LDS를 구하면.. 5,4,3,2,1 이후 5기준으로(포함한) 나머지 요소에서의 LIS는 1,5
두 배열을 합하고 5를 하나 빼주면 6이런 방식으로 풀이된다.
최종적으로 다 계산해보면
{1},1 {1} , 1
{5,4,3,2,1},5 {1,5}, 2
{2,1},2 {1,2}, 2
{1},1 {1}, 1
{4,3,2,1},4 {1,2,4} , 3
{3,2,1},3 {1,2,3} , 3
{4,2,1},3 {1,2,3,4}, 4
{5,2,1},3 {1,2,3,4,5}, 5
{2,1},2 {1,2} 2
{1}, 1 {1}, 1
아래와 같이 겹치는 요소하나를 제거해주면 바이토닉 수열이 나온다.
LDS + LIS -1
{1}, 1
{1,5,4,3,2,1}, 6
{1,2,1}, 3
{1}, 1
{1,2,4,3,2,1}, 6
{1,2,3,2,1}, 5
{1,2,3,4,2,1}, 3
{1,2,3,4,5,2,1},7
{1,2,1}, 3
{1}, 1
이전 LIS, LDS를 구할 때, dp 테이블의 값을 내마음대로 정의해서 썼는데 그 경우엔 이렇게 바이토닉을 구할 수 없다.
(LDS + LIS -1 연산을 할 때 예외가 발생하겠지)
따라서 이런 응용 문제를 해결하기 위해서라도 정형화 또는 정석적인 방식으로만 익히는게 더 좋은 학습법이라 생각된다. (아래의 LIS,LDS를 잘 기억하도록)
//11054
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
//https://st-lab.tistory.com/136
static Integer[] arr;
static Integer[] rdp;
static Integer[] ldp;
static Integer[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
arr = new Integer[N];
rdp = new Integer[N];
ldp = new Integer[N];
dp = new Integer[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; ++i)
arr[i] = Integer.parseInt(st.nextToken());
/* TopDown
for (int i = 0; i < N; ++i) {
LIS(i, rdp);
LDS(i, ldp);
}
//
*/
//Bottom-UP
for ( int i = 0 ; i < N ; ++i) {
rdp[i]=1;
for (int j = 0; j < i ; ++j) {
if ( arr[j] < arr[i])
rdp[i] = Math.max(rdp[i], rdp[j] + 1);
}
}
for ( int i = N-1 ; i >= 0 ; --i) {
ldp[i]=1;
for (int j = N-1; j > i ; --j) {
if ( arr[j] < arr[i])
ldp[i] = Math.max(ldp[i], ldp[j] + 1);
}
}
int max = Integer.MIN_VALUE;
for ( int i = 0 ; i < N ; ++i) {
max = Math.max(max,rdp[i] + ldp[i] - 1);
}
System.out.println(max);
br.close();
}
static int LIS(int n, Integer[] dp) {
if (dp[n] == null) {
dp[n] = 1;
for (int i = n - 1; i >= 0; --i) {
if (arr[i] < arr[n]) {
dp[n] = Math.max(dp[n], LIS(i, dp) + 1);
}
}
}
return dp[n];
}
static int LDS(int n, Integer[] dp) {
if (dp[n] == null) {
dp[n] = 1;
for (int i = n + 1; i < arr.length; ++i) {
if (arr[i] < arr[n])
dp[n] = Math.max(dp[n], LDS(i, dp) + 1);
}
}
return dp[n];
}
}
ex)
10
1 5 2 1 4 3 4 5 2 1
LIS : 1 2 2 1 3 3 4 5 2 1
LDS : 1 5 2 1 4 3 3 3 2 1
7
출처 : [백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바] (tistory.com)
