![[백준,BOJ 11054] 가장 긴 바이토닉 부분 수열(JAVA 구현,추가풀이)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fb5YrhV%2Fbtqz5crV2LJ%2FWVVzpY0Trt63JNJLKwND8k%2Fimg.png)
-내 생각
이 문제를 이해할 때 주의해야 할 점이 하나 있는데, 바이 토닉 부분 수열과 바이 토닉 수열의 구분을 확실히 해야 한다. 이 문제에서 묻는 대상은 바이 토닉 부분 수열이기 때문에 문제에서 예로 든 {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이 토닉 수열이 아니라는 것이다.
처음 구현하기에 앞서 바이 토닉 부분 수열의 경우 가장 큰 값을 기준으로 왼쪽으로는 작은 값을 갖고, 오른쪽으로는 큰 값을 가지는 것을 보고 우선 가장 큰 값을 찾은 후 왼쪽부터 증가하다가 큰 값을 만나면 그 이후부터는 작은 값을 처리해 주려고 했지만, 구현에 실패해서 다른 분들의 글을 통해 도움을 받았다.
-해법
우선 이 문제를 풀기 위해서는 LIS라는 개념이 완벽하게 자리 잡고 있어야 한다. 그러기 위해서는 가장 긴 부분 증가수열과 가장 긴 부분 감소 수열에 대해서 알고 있어야 한다. 해당 내용들은 블로그 내에 존재하니 필요하면 확인하기 바란다.
요점은 -> 방향으로 숫자를 볼 땐 가장 큰 값을 기준으로 작은 숫자를 선택하지만, 반대로 <- 방향으로 숫자를 본다면, 처음과 마지막에서 출발해서 큰 숫자만을 찾으면 되는 것이다. 즉, 위에서 언급한 두 내용이 사용된다는 것이다. 이후 가장 큰 숫자를 기준으로 본다면 -> 방향으로 점점 커지는 숫자와 작아지는 숫자를 동시에 확인할 수 있다. 아래 표를 보자.
| 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 |
위와 같이 표가 완성될 수 있다. 왼쪽에서부터 출발한 것이 첫 번째 결과이고, 반대가 두 번째 결과이다. 이렇게 만들어진 표를 자세히 보면 가장 큰 값을 기준으로 왼쪽은 점점 커지는 숫자, 오른쪽은 점점 작아지는 숫자의 개수를 알 수 있다. 이 경우 첫 번째 5와 두 번째 5가 존재하는데, 첫 번째 5일 경우, 왼쪽에서 1 하나가 존재하고, 오른쪽에서 4, 3, 2, 1이 존재하는 것을 확인할 수 있다. 5는 중복이므로 2+5 -1 을하면 6의 결과가 나오고, 두 번째 5의 경우는 왼쪽에서 1, 2, 3, 4를 선택하고 오른쪽에서 1, 2를 선택한다. 역시 5는 중복이므로 5 + 2 -1을 하면 7의 결과가 나오므로 최장 길이로 만들 수 있는 가장 긴 바이 토닉 부분 수열의 길이는 7이 된다.
즉, 결과적으로 위의 표의 상태에서 각 열들을 모두 더해, 가장 큰 값을 찾고 -1을 해주면 정답이 되는 것이다.
이제 코드를 보자
import java.util.*;
public class Main {
static int n;
static int dp[][], cost[]; // 메모이제이션 배열을 2차원 배열로 선언하여 LIS, LDS를 수행
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
dp = new int[2][n+1];
cost = new int[n+1];
for(int i=1;i<=n;i++) {
cost[i] = sc.nextInt();
}
dp[1][n] =1; // 오른쪽에서 시작하는 LIS
dp[0][1] = 1; // 왼쪽에서 시작하는 LIS
for(int i=n-1;i>0;i--) { // 오른쪽에서 시작하는 LIS
dp[1][i] =1;
for(int j=n;j>i;j--) {
if(cost[i]>cost[j]) {
dp[1][i] = Math.max(dp[1][i], dp[1][j]+1);
}
}
}
for(int i=2;i<=n;i++) { // 왼쪽에서 시작하는 LIS
dp[0][i] =1;
for(int j=1;j<i;j++) {
if(cost[i]>cost[j]) {
dp[0][i] = Math.max(dp[0][i], dp[0][j]+1);
}
}
}
int max = Integer.MIN_VALUE;
for(int i=1;i<=n;i++) { // 두 배열의 값들을 더해준다.
dp[0][i] += dp[1][i];
}
for(int i=1;i<=n;i++) {
if(dp[0][i] > max) {
max = dp[0][i];
}
}
System.out.println(max-1); // 최댓값을 찾아 -1 해주면 정답
}
}
바이 토닉 수열은 가장 큰 값을 기준으로 왼쪽은 오름차순, 오른쪽은 내림차순이라 볼 수 있다. 하지만 이건 가장 왼쪽에서 오름차순, 가장 오른쪽에서 오름차순이라는 소리와 같다. 그렇기에 가장 긴 증가하는 부분 수열 LIS를 왼쪽과 오른쪽에서 수행해주면 된다. 이외의 요점은 위의 설명과 같다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int a[] = new int[n];
int l_dp[] = new int[n];
int r_dp[] = new int[n];
for(int i=0;i<n;i++) {
a[i] = in.nextInt();
}
// LIS
for(int i=0;i<n;i++) {
l_dp[i] = 1;
for(int j=0;j<i;j++) {
if(a[j]<a[i] && l_dp[i] < l_dp[j]+1) {
l_dp[i] = l_dp[j]+1;
}
}
}
// LDS
for(int i=n-1;i>=0;i--) {
r_dp[i] = 1;
for(int j=n-1;j>i;j--) {
if(a[j]<a[i] && r_dp[i] < r_dp[j]+1) {
r_dp[i] = r_dp[j]+1;
}
}
}
int max = Integer.MIN_VALUE;
// LIS와 LDS의 부분수열 길이의 합 중 최댓값을 찾는다.
for(int i=0;i<n;i++) {
if(max<l_dp[i]+r_dp[i]) {
max = l_dp[i] + r_dp[i];
}
}
// 중복 제거를 위한 -1
System.out.println(max - 1);
in.close();
}
}