[JAVA] BOJ(백준) - 가장 긴 바이토닉 부분 수열 - 11054

문제내용

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

11054번: 가장 긴 바이토닉 부분 수열

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

---

문제 접근 방법

처음 이문제를 접했을대 전에 풀었던 가장 긴 증가하는 부분 수열을 활용해 풀면 된다 생각했고,

전에 풀었던 문제가 다른점은 증가하는부분이 있고, 감소하는 부분이 있다는 것이었다.

 

먼저 바이토닉 부분 수열은

증가만 해도되고, 감소만 해도되고, 증가한뒤에 감소해도 되는 수열이다.

 

위의것을 고려해서 처음에 줬던 조건은

1. A수열의 최대값이 있는 인덱스 위치를 찾는다.

2. 만약 같은값으로 최대값이 2개이상 있다면 뒤에 있는 최대값의 인덱스를 기준값으로 한다.

3. 0~n-1까지 돌때 기준값 전에는 증가하는 수열을, 기준값 뒤에는 감소하는 수열의 길이를 구한다.

 

3가지를 생각하고 문제를 풀었고, 이때 핵심은 언제까지 증가하고, 언제부터 감소하냐 이다.

이렇게 풀었을때 문제 예시에서준것은 맞았지만 다른 반례에서 틀린 코드가 됐다.

 

이유는

첫번째로 최댓값이 첫번째 혹은 마지막에 있을때 문제가 생기고

두번째로 최대값이 중간에 있다고해도 최대값이 같은게 두개이상 있을때 앞에 있는 최댓값을 기준으로 했을때가 더 긴 수열이 나올수가 있다는 문제점이 있다.

 

결국에는 내가 처음에 작성했던 코드는 증가에서 감소로 바뀌게 해주는 기준값을 제대로 찾지 못했던게 틀린코드가 된 원이이라고 할 수 있다.

 

기준값을 효율적으로 찾기 위해 고민하고 구글링해본 결과 좋은 방법을 찾아냈다.

아래 방법은 기준값을 찾아낸다기 보다는 자동으로 찾아지는(?) 방법이다.

 

그 방법은 증가하는 수열과 감소하는 수열을 구하고 각 수열의 최댓값이 되게 하는 지점이 기준값이 된다.

즉, 바이토닉 수열 = 증가하는 수열의 최댓값 + 감소하는 수열의 최댓값 이라고 할수 있다.

 

1. 먼저 dp배열을 두가지로 정의한다. dpUp(증가하는 수열) 과 dpDown(감소하는 수열)을 정의해준다.

2. 증가하는 수열의 경우 '가장 긴 증가하는 부분 수열'의 문제와 같은 코드로 작성한다.

3. 감소하는 수열의 경우 뒤에서 부터 체크하며 수열의 길이를 dpDown에 저장한다.

• 그렇게하는 이유는 dpDown을 앞의 인덱스부터 저장해나갈 경우 dpUp의 최댓값과 만나는 지점의 기준값이 엉뚱하게 잡히면서 틀린 코드가 된다.
•  

  Idx	0	1	2	3	4	5	6	7	8
  A	5	1	6	2	7	3	7	2	1

  위의 표를 보면 바이토닉수열은 {1 2 3 7 2 1} , 증가하는 수열은 { 1 2 3 7 }, 감소하는 수열은 {7 2 1} 이 되야한다. 만약 dpDown을 앞에서부터 저장해나가면 {5 3 2 1}이 되고 이는 바이토닉 수열이 아니게 된다.

4. 0~n-1까지 순회하며 dpUp[i]와 dpDown[i]가 최대가되는 부분을 구하면 바이토닉 수열의 길이를 알 수 있다.

 

풀이를 보자.

 

---

풀이

BottomUp

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

public class Main {
	static int[] A;
	static int[] dpUp;
	static int[] dpDown;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int n = Integer.parseInt(br.readLine());
		A = new int[n];
		dpUp = new int[n];
		dpDown = new int[n];
		st = new StringTokenizer(br.readLine()); 
		
		for(int i=0; i<n; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		dpUp[0]=1; //증가 dp 첫번째 원소 초기화
		dpDown[n-1]=1; //감소 dp 마지막 원소 초기화
		
		//증가부분
		for(int i=1; i<n; i++) {
			dpUp[i] = 1;
			for(int j=0; j<n; j++) {
				if(A[j]<A[i] && dpUp[i]<=dpUp[j]) {
					dpUp[i] = dpUp[j] + 1;
				}
			}
		}
		
		//감소부분의 경우 뒤에서 부터 검사하기 때문에 n-2부터 시작.
		//뒤에서부터 시작하는 이유는 후에 증가dp와 감소dp가 최대가 되는 지점에서
		//만나는 인덱스를 넣었을때 감소dp는 뒤에서부터 시작한 감소부분수열길이가 되야함.
		for(int i=n-2; i>=0; i--) {
			dpDown[i]=1;
			for(int j=n-1; j>0; j--) {
				if(A[j]<A[i] && dpDown[i]<=dpDown[j]) {
					dpDown[i] = dpDown[j] + 1;
				}
			}
		}
		
		int max = Integer.MIN_VALUE;
		for(int i=0; i<n; i++) {
			max = Math.max(max, dpUp[i]+dpDown[i]);
		}
		//만나는 지점의 인덱스값은 겹치니까 -1해줌.
		System.out.println(max-1);
	}
}

 

TopDown

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

public class BOJ_11054_2 {
	static int[] A;
	static int[] dpUp;
	static int[] dpDown;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int n = Integer.parseInt(br.readLine());
		A = new int[n];
		dpUp = new int[n];
		dpDown = new int[n];
		st = new StringTokenizer(br.readLine()); 
		
		for(int i=0; i<n; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		dpUp[0]=1; //증가 dp 첫번째 원소 초기화
		dpDown[n-1]=1; //감소 dp 마지막 원소 초기화
		
		int max = Integer.MIN_VALUE;
		for(int i=0; i<n; i++) {
			max = Math.max(max, LIS(i)+LDS(i));
		}
		
		//만나는 지점의 인덱스값은 겹치니까 -1해줌.
		System.out.println(max-1);
	}
	
	public static int LIS(int n) {
		if(dpUp[n]==0) {
			dpUp[n] = 1;
			//0부터 원소값 n전까지 탐색
			for(int i=0; i<n; i++) {
				if(A[n]>A[i]) {
					dpUp[n] = Math.max(dpUp[n], LIS(i)+1); 
				}
			}
		}
		return dpUp[n];
	}
	
	public static int LDS(int n) {
		if(dpDown[n]==0) {
			dpDown[n] = 1;
			//n다음 원소부터 탐색
			for(int i=n+1; i<A.length; i++) {
				if(A[n]>A[i]) {
					dpDown[n] = Math.max(dpDown[n], LDS(i)+1);
				}
			}
		}
		return dpDown[n];
	}
}

---

마치며

위 방법으로 재귀역시 가능하다. LIS부분의 함수는 전에 했던 방식 그대로 LDS부분의 함수만 만들어주면 풀린다.

어쨌든 이번문제는 기준값을 어떻게 줄것인가를 생각해내는 것이 가장큰 핵심이라고 생각한다.