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

문제

 

---

풀이

 

해당 문제를 풀기 위해서는

저번 시간에 배웠던 LIS 개념을 써야한다.

이전에 배웠던 개념을 활용하니 금방 해결할 수 있었다.

LIS에 대해 잘 모르겠다면 아래 글을 먼저 보고 오면 좋을 이해하는데 도움이 될 것 같다.

 

https://inscowoo.tistory.com/37

[백준] 11053. 가장 긴 증가하는 부분 수열(LIS) - JAVA

 

해당 문제를 보면 증가하다가 감소하는 바이토닉 수열 중 가장 긴 수열을 찾아야 한다.

즉, 증가->감소하는 바이토닉 수열중 가장 긴 수열을 찾기위해서

(증가한 길이 + 감소한 길이) 가 이 수열에서 가장 긴 바이토닉 수열이다.

 

따라서 증가하는 수열과 감소하는 수열의 길이를 둘 다 찾아 주어야 한다.

 

1	5	2	1	4	3	4	5	2	1
1	2	2	1	3	3	4	5	2	1

 

5까지 도달하는 경우인

{1, 5, 2, 1, 4, 3, 4, 5, 2, 1} 인 부분 수열이 가장 길다.

 

그리고 감소하는 수열을 찾기 위해

뒤에서 부터 실행해서 실행한다면
가장 긴 감소하는 수열을 찾을 수 있다.

 

1	5	2	1	4	3	4	5	2	1
1	5	2	1	4	3	3	3	2	1

 

{1, 5, 2, 1, 4, 3, 4, 5, 2, 1}

 

 

그렇게 아래처럼 각각의 위치에서 수열의 길이를 구했다.

1	5	2	1	4	3	4	5	2	1
1	2	2	1	3	3	4	5	2	1
1	5	2	1	4	3	3	3	2	1

 

이제 가장 긴 바이토닉 수열을 찾기위해서는

첫번째 수열[i] + 두번째 수열[i] 값이 가장 큰 것이

가장 긴 바이토닉 수열의 증가하다가 감소하는 지점이 된다

 

{ 1, 5, 2, 1, 4, 3, 4, 5, 2, 1 }

따라서 7번째 인덱스가 8이 나오면서 가장 긴 바이토닉 수열이다.

 

해당 문제에서는 수열의 길이를 구하는게 정답이다.

그래서 길이를 구할 때는 겹치는 i 번째를 한번 제외해야하기 때문에

첫번째 수열[i] + 두번째 수열[i] -1 가 해당 수열에서 가장 긴 수열의 길이가 됨으로 답이 된다.

 

 

---

코드

 

import java.io.*;

import java.util.*;

 

public class Main{

static int[] arr;

static int[] DP1;

static int[] DP2;

static int size;

 

static void LIS(){

//DP1 LIS 증가순

for(int i=1; i<size; i++){

for(int k=0; k<i; k++){

if(arr[i]>arr[k]){

DP1[i] = Math.max(DP1[i] , DP1[k]+1);

}

}

}

 

//DP2 LIS 감소순

for(int i=size-2; i>=0; i--){

for(int k=i+1; k<size; k++){

if(arr[i] > arr[k]){

DP2[i] = Math.max(DP2[i], DP2[k]+1);

}

}

}

 

}

 

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

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

size = Integer.parseInt(st.nextToken());

arr = new int[size];

DP1 = new int[size];

DP2 = new int[size];

st = new StringTokenizer(br.readLine());

for(int i=0; i<size; i++){

arr[i] = Integer.parseInt(st.nextToken());

}

Arrays.fill(DP1,1);

Arrays.fill(DP2,1);

LIS();

 

int result = 1;

for(int i=0; i<size; i++){

result = Math.max(result, DP1[i]+DP2[i]-1);

}

System.out.print(result);

}

}