[백준알고리즘-JAVA]11054번 풀이(가장 긴 바이토닉 부분 수열) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 11054번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

입력 예시

10
1 5 2 1 4 3 4 5 2 1

출력 예시

7

성공 코드

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

public class Main {

	static int N ;
	static Integer[] arr;
	static Integer[] dp_left;
	static Integer[] dp_right;
	static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());;
		
		arr = new Integer[N];
		dp_left = new Integer[N];
		dp_right = new Integer[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0 ; i < N ; i++) {
				arr[i]=Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0 ; i < N ; i ++) {
			left(i);
			right(i);
	}

		for(int i = 0 ; i < N ;i++)
			max = Math.max(max, dp_left[i]+dp_right[i]);
		
		System.out.println(max-1);
}
	public static int left(int num) {
		if(dp_left[num]==null) {
			dp_left[num]=1;
			for(int i = num-1 ; i >= 0 ; i --) {
				if(arr[num] > arr[i]) {
					dp_left[num] = Math.max(left(i)+1, dp_left[num]);
				}
			}
			
		}
		return dp_left[num];
	}
	public static int right(int num) {
		if(dp_right[num]==null) {
			dp_right[num]=1;
			for(int i = num ; i < N ; i ++) {
				if(arr[num] > arr[i]) {
					dp_right[num] = Math.max(right(i)+1, dp_right[num]);
				}
			}
		}
		return dp_right[num];
	}
}

가장 긴 바이토닉 부분 수열 알고리즘을 풀기 전에 반듯이 아래 링크의 설명을 듣고 와야지 아주 쉽게 풀 수 있습니다.

[백준알고리즘-JAVA]11053번 풀이(가장 긴 증가하는 부분 수열) - 초보도 이해하는 풀이

 

해당 알고리즘에서 가장 중요한 점은 어떻게 DP를 표현할 것인가입니다.

이 점이 바로 해결책에 가장 가깝게 갈 수 있기 때문입니다!

 

STEP을 따라가며 이해해 보도록 하죠

---

알고리즘 흐름도

 입력받기 -> 왼쪽, 오른쪽 증가수열 DP 구하기 -> 왼쪽, 오른쪽 증가수열 더하여 최댓값 찾아 출력하기

---

STEP1 문제 이해하기

문제는 간단합니다 왼쪽에서 오른쪽으로 갈수록 증가나 감소가 변하면 안 된다.

 

10 20 30 25 20 과같이 30을 기점으로 증가하고 감소하던가

10 20 30 40처럼 쭉 증가하던가

50 40 25 10처럼 쭉 감소하던가

이러한 수열들이 바로 문제에서 원하는 부분 수열입니다.

 

그렇다면 이제 이러한 관점을 가지고 다음 STEP으로 넘어가 보죠

---

STEP2 DP 이해하기

 이번 문제의 핵심이기도 하죠 DP를 잘 이해해야 재귀를 구현할 수 있기 때문이죠

 

어떻게 이런 문제를 풀이할까요??

 

이전에 보았던 증가하는 부분 수열을 참고해 보면 증가하는 부분은 찾을 수 있습니다.

감소하는 부분은 증가하는 부분 수열을 거꾸로 하면 쉽게 해결할 수 있죠

 

그렇다면 증가와 감소를 같이 판별하려면 어떻게 해야 할까요?

 

표로 보고 다시 한번 생각해 보도록 하죠

 

증가하는 수열 (왼쪽부터 증가하는 수열 생각)

ARR	10	20	30	40
DP	1	2	3	4

감소하는 수열 (오른쪽부터 증가하는 수열을 생각)

ARR	50	40	25	10
DP	4	3	2	1

흠... 아직 감이 잡히지 않습니다. 그러면 아래 표를 보며 생각해 보도록 하죠

 

ARR	10	20	30	25	20
DP(증가)	1	2	3	3	2
DP(감소)	1	1	3	2	1

이런 식으로 표현이 되죠

 

그러면 이 2가지를 더하면

ARR	10	20	30	25	20
DP	2	3	6	5	3

이런 식으로 표현이 됩니다. 이 중의 가장 최댓값을 꺼내오면 바로 30이 되고 6이 됩니다. 그러나 이 값은 왼쪽, 오른쪽에서 증가하는 수열을 더한 값으로 바로 자기 자신의 값을 2번 포함하게 되어있죠

 

이에 따라서 -1을 해주면 저희가 원하는 답이 나오게 됩니다.

 

물론 처음에 바로 생각하기란 쉽지 않습니다. 그러나 포기하지 마시고 여러 문제를 접하고 이러한 방법도 있다고 기억하시는 것만으로도 충분한 공부가 됩니다.

 

조금 더 이해를 돕기 위해 다음 STEP을 따라가 완벽히 이해 보도록 하죠

---

STEP 3 재귀 구현하기

우선 이전에 풀어보았던 오니 쪽에서 증가하는 수열은 먼저 살펴보겠습니다.

public static int left(int num) {
		if(dp_left[num]==null) {
			dp_left[num]=1;
			for(int i = num-1 ; i >= 0 ; i --) {
				if(arr[num] > arr[i]) {
					dp_left[num] = Math.max(left(i)+1, dp_left[num]);
				}
			}
			
		}
		return dp_left[num];
	}

아주 비슷합니다. 이전 글에 발행된 가장 긴 부분 수열 알고리즘과 굉장히 유사합니다.

 

예시로 들어가서 확인해보도록 하죠 -> 1 5 2 1 4 3 4 5 2 1

arr	1	5	2	1	4	3	4	5	2	1
dp_left	null	null	null	null	null	null	null	null	null	null

 

재귀 인자로 0을 넣어준다.

 - 첫 번째 if문에 걸린다. 

 - dp [0]에 1을 넣는다.

 - for문 조건을 만족하지 못하여 for문을 통과한다 dp [0] = 1을 반환한다.

arr	1	5	2	1	4	3	4	5	2	1
dp_left	1	null	null	null	null	null	null	null	null	null

- 재귀 인자로 1을 넣어준다.

 - 첫 번째 if문에 거린다. 

 - dp [1]에 1을 넣는다.

 - for문 수행한다. (int i = 0)

 - arr [1] > arr [0]을 만족함으로 for문안의 if문을 수행한다.

 - dp [1] = Math.max(dp [1], left(1)+1)을 비교한다. (dp [1]=1 // left(1)+1 = dp [0]+1 = 1 + 1 = 2)

 - dp [1] = 2를 넣어준다.

arr	1	5	2	1	4	3	4	5	2	1
dp_left	1	2	null	null	null	null	null	null	null	null

이런 식으로 인자를 0에서부터 넣어주면서 모든 dp_left를 채워주면 기존에 풀어보았던 증가하는 부분 수열 탐색 끝

---

이와 같은 방식이지만 반대로 오른쪽부터 증가하는 수열을 하기 위해서는 그냥 반대로만 작성해 주면 끝

public static int right(int num) {
		if(dp_right[num]==null) {
			dp_right[num]=1;
			for(int i = num ; i < N ; i ++) {
				if(arr[num] > arr[i]) {
					dp_right[num] = Math.max(right(i)+1, dp_right[num]);
				}
			}
		}
		return dp_right[num];
	}

간단합니다. 이해가 되지 않으시면 위에 처럼 표를 만들어서 하나씩 채워나가시면 이해가 되실 겁니다.

여기 for문은 왜 ++이느냐? 하는 의문은 위는 이제 이전 값이 자신보다 작아야 하지만,

 

right의 경우 이전 값이 자신보다 커야 합니다. 그니깐 들어오자마자 모든 arr을 탐색하면서 자신보다 작은 수를 찾아 올려 줍니다.

 

뭐 main에서 left를 상위부터 값을 넣어준다면, 똑같이 실행이 되긴 합니다.

 

이런 식으로 값을 구한 뒤 dp를 아래와 같이 비교하여 출력하면 끝

for(int i = 0 ; i < N ; i ++) {
			left(i);
			right(i);
	}

		for(int i = 0 ; i < N ;i++)
			max = Math.max(max, dp_left[i]+dp_right[i]);
		
		System.out.println(max-1);