[백준 / Java] 11054번: 가장 긴 바이토닉 부분 수열 (골드4)

문제 풀이 날짜: 2023.05.12
포스트 작성일: 2023.05.18

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 11054번: 가장 긴 바이토닉 부분 수열 (골드4) (문제 링크)

 

키워드

동적 계획법(DP)

 

풀이 접근법

• 가장 긴 증가하는 부분 수열(LIS)의 응용 문제이다. (백준 온라인 저지 11053번 문제 링크)
• 이전에 LIS를 풀어본 적이 있어서 비교적 접근이 쉬웠다. LIS는 현재 가리키는 수(arr[i])를 기준으로 그 이전에 존재하는 수들과 (arr[j], j = 0 ~ i-1) 비교하면서, 이전의 수(arr[j])보다 현재 가리키는 수(arr[i])가 더 크다면 이것을 증가하는 부분 수열에 합치고 현재까지의 최대 길이를 갱신하는(DP[j] + 1) 문제였다.
• 그런데 바이토닉 부분 수열은 증가하다가 감소하는 터닝포인트가 있는 수열이다. 
• 반드시 수의 크기가 증가하다가 감소하는 터닝포인트가 존재하며, 그 부분을 기점으로 앞으로는 더 큰 값을 수열에 포함시킬지 더 작은 값을 포함시킬지를 결정한다. 길이보다도 대소비교의 전환을 핵심으로 두고 풀었다.
  • DP 배열을 2차원으로 선언해서 증가할 때의 길이[0], 감소할 때의 길이[1]를 각각 기록한다.
  • LIS 문제와 같은 형태로 이중 for문을 이용해 수를 탐색한다. 현재 i가 가리키는 수를 기점으로 그 이전의 값들을 탐색한다.
  • 앞 부분은 그냥 LIS와 같이 증가하는 수열을 찾으며 길이를 기록하는데, 다음에 탐색할 수가 현재의 수보다 작으면서도  DP[j][0] > DP[j][1] 인 시점이 나타나면 그곳이 터닝포인트다.
  • 즉, 해당 숫자까지 증가하는 수열의 길이(DP[j][0])가 감소하는 수열의 길이(DP[j][1])보다 훨씬 길 때를 ‘증가하다가 감소하는 포인트’로 삼는다.

코드

import java.io.*;
import java.util.StringTokenizer;

public class Q11054 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int[][] DP = new int[N][2];
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			DP[i][0] = 1; //증가하는 구간에서의 길이
			DP[i][1] = 0; //감소하는 구간에서의 길이
		}
		
		for(int i = 1; i < N; i++) {
			int target = arr[i];
			for(int j = 0; j < i; j++) {
				if(arr[j] < target) { //증가
					DP[i][0] = Math.max(DP[j][0] + 1, DP[i][0]);
				}
				else if(arr[j] > target) { //감소
					if(DP[j][0] > DP[j][1]) { //증가하다가 감소하는 포인트라면
						DP[i][1] = Math.max(DP[j][0] + 1, DP[i][1]);
					}
					else {
						DP[i][1] = Math.max(DP[j][1] + 1, DP[i][1]);
					}
				}
			}
		}
		
		int result = -1;
		for(int i = 0; i < N; i++) {
			int max = Math.max(DP[i][0], DP[i][1]);
			if(max > result) {
				result = max;
			}
		}
		
		System.out.print(result);
	}

}

---

이전에 LIS를 풀 때는 많이 틀리기도 했고, 도저히 풀리지 않아서 다른 사람의 풀이법을 참고해서 코드를 작성했었다. 하지만 한 번 풀이방식에 익숙해지고 나니 LIS처럼 푸는 사고방식이 머리에 정착되었고, 응용문제는 비교적 쉽게 풀 수 있었다. DP 문제는 DP식 사고방식을 내것으로 만드는 게 정말 중요한 것 같다. 이 외에도 다양한 DP 응용 문제들이 있으니 꼭 한 번은 풀어보아야겠다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week7/day7/Q11054.java