[백준] 11054

백준 11054번 문제 풀이: 가장 긴 바이토닉 부분 수열

문제 설명

백준 11054번 문제는 주어진 수열에서 가장 긴 바이토닉 부분 수열을 찾는 문제입니다. 바이토닉 부분 수열은 증가하는 부분 수열이 하나 존재하고, 그 뒤에 감소하는 부분 수열이 이어지는 수열을 의미합니다. 따라서 이 문제는 두 개의 부분 수열을 합쳐서 가장 긴 길이를 구하는 문제입니다.

문제 해결 접근 방법

이 문제를 해결하기 위해 동적 프로그래밍(DP) 접근법을 사용했습니다. 이를 위해 수열의 각 원소를 기준으로 왼쪽에서 오른쪽으로 증가하는 부분 수열과 오른쪽에서 왼쪽으로 감소하는 부분 수열을 각각 구한 후, 두 부분 수열의 합이 최대가 되는 값을 찾습니다.

단계별 접근 방법:

1. DP 배열 정의:

   • increase[i]는 i번째 원소까지의 증가하는 부분 수열의 최대 길이입니다.
   • decrease[i]는 i번째 원소부터 시작하는 감소하는 부분 수열의 최대 길이입니다.

2. 증가하는 부분 수열 계산:

   • 왼쪽에서 오른쪽으로 순회하면서 현재 원소보다 작은 값을 가지는 이전 원소들 중 가장 큰 증가 부분 수열 길이에 1을 더해 현재 원소의 증가 부분 수열 길이를 갱신합니다.

3. 감소하는 부분 수열 계산:

   • 오른쪽에서 왼쪽으로 순회하면서 현재 원소보다 작은 값을 가지는 이후 원소들 중 가장 큰 감소 부분 수열 길이에 1을 더해 현재 원소의 감소 부분 수열 길이를 갱신합니다.

4. 바이토닉 부분 수열 길이 계산:

   • 각 원소를 기준으로 증가 부분 수열 길이와 감소 부분 수열 길이를 합친 값 중 최대 값을 찾습니다.

코드 구현

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" "); // "1 2 3 4"

        int[] numbers = new int[n+1];
        int[] increase = new int[n+1];
        int[] decrease = new int[n+1];

        // 입력 값 초기화
        for(int i = 1; i <= n; i++){
            numbers[i] = Integer.parseInt(line[i-1]);
        }

        // 증가 부분 수열 계산
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++){
                if(numbers[j] < numbers[i]){
                    increase[i] = Math.max(increase[j] + 1, increase[i]);
                }
            }
        }

        // 감소 부분 수열 계산
        for(int i = n; i >= 1; i--){
            for(int j = n; j > i; j--){
                if(numbers[j] < numbers[i]){
                    decrease[i] = Math.max(decrease[j] + 1, decrease[i]);
                }
            }
        }

        // 바이토닉 부분 수열의 최대 길이 계산
        int answer = 0;
        for(int i = 1; i <= n; i++){
            answer = Math.max(answer, increase[i] + decrease[i] - 1);
        }

        System.out.println(answer);
    }
}

디버깅 경험

코드를 작성하면서 몇 가지 중요한 문제를 해결해야 했습니다:

1. 인덱스 관리:

   • Java 배열 인덱스는 0부터 시작하기 때문에, 수열의 편의상 인덱스를 1부터 사용하였습니다. 따라서 numbers, increase, decrease 배열의 크기를 n+1로 정의하였고, 각 배열의 인덱스 1부터 n까지 사용하였습니다.

2. DP 배열 초기화:

   • increase 배열의 초기값은 모두 0으로 초기화하였고, decrease 배열의 마지막 값은 0으로 초기화하였습니다. 이를 통해 수열의 처음과 끝에서의 비교를 용이하게 하였습니다.

결론

이 문제를 해결하면서 동적 프로그래밍의 기본 원리와 배열 인덱스 관리의 중요성을 다시 한 번 느낄 수 있었습니다. 특히, 증가 부분 수열과 감소 부분 수열을 각각 계산한 후 이를 합쳐서 바이토닉 부분 수열의 최대 길이를 구하는 접근 방법이 유용하다는 것을 배웠습니다. 앞으로도 이러한 문제 해결 방법을 통해 더욱 효율적인 코딩을 할 수 있도록 노력하겠습니다.