[백준/BOJ] 11054번 : 가장 긴 바이토닉 부분 수열 (+ 11053번, 11054번 풀이 포함)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11054번 : '가장 긴 바이토닉 부분 수열' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 동적 계획법(DP)에 대한 이해가 필요합니다.

BOJ 단계별로 풀어보기의 15단계 '동적 계획법'에 해당되는 문제입니다.

 

 

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

 

수열 중 일부를 선택해서 만든 증가하다가 감소하는 부분 수열을 바이토닉 부분 수열이라고 할 때, 가장 긴 바이토닉 부분 수열의 길이를 찾는 문제입니다.

이 문제를 풀이하기 위해서는 선행적으로 백준 11053번 : '가장 긴 증가하는 부분 수열' 문제에 대한 풀이를 응용해야 합니다.

 

해당 이전에 풀이한 적이 있었는데, 조금 더 다듬어진 풀이를 작성하고자 아래의 접은 글에 짧게 정리해보겠습니다.

↓ 11053번 : '가장 긴 증가하는 부분 수열' 풀이

 

위의 문제 역시 DP로 O(N log N) 시간에 해결이 가능합니다.

풀이를 간단하게 적어보겠습니다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    int arr[1005]; for(int i=0; i<N; i++) cin >> arr[i];
    int dp[1005]; fill(dp, dp+1005, 1);

    int ans = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<i; j++)
            if(arr[i] > arr[j]) dp[i] = max(dp[i], dp[j]+1);
        ans = max(ans, dp[i]);
    }
    cout << ans;
}

 

위 코드의 원리는 현재 위치(i번째) 기준으로 j = 0 ~ i-1 중에서 arr[i] > arr[j]이면 dp[j]+1의 길이로 새로운 가장 긴 증가하는 부분 수열을 만들어주는 것입니다.

위와 같이 풀이 코드를 작성하여 문제를 풀 수 있습니다.

 

풀이한 김에 비슷한 예시로 11722번 : '가장 긴 감소하는 부분 수열' 문제도 풀이해보겠습니다.

↓ 11722번 : '가장 긴 감소하는 부분 수열' 풀이

 

비슷한 문제인데 증가 수열이 아닌 감소 수열을 구하는 문제입니다.

같은 방식으로 조건문만 바꾸어주면 풀이할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    int arr[1005]; for(int i=0; i<N; i++) cin >> arr[i];
    int dp[1005]; fill(dp, dp+1005, 1);

    int ans = 1;
    for(int i=0; i<N; i++)
        for(int j=0; j<i; j++) {
            if(arr[i] < arr[j]) dp[i] = max(dp[i], dp[j]+1);
            ans = max(ans, dp[i]);
        }
    cout << ans;
}

 

arr[i] < arr[j] 부분과 같이 부등호의 방향만 바꾸어주면 똑같이 풀이가 가능합니다.

 

이제 가장 긴 바이토닉 부분 수열의 길이를 구할 것인데, 이것은 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 접목시켜 모든 자리에 대해서 검사를 하여 두 수열의 길이의 합이 가장 긴 것을 구하면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    int arr[1005]; for(int i=0; i<N; i++) cin >> arr[i];
    int dp[2][1005]; fill(&dp[0][0], &dp[1][1005], 1);

    for(int i=0; i<N; i++)
        for(int j=0; j<i; j++)
            if(arr[i] > arr[j]) dp[0][i] = max(dp[0][i], dp[0][j]+1);
    for(int i=N-1; i>=0; i--)
        for(int j=N-1; j>i; j--)
            if(arr[i] > arr[j]) dp[1][i] = max(dp[1][i], dp[1][j]+1);

    int ans = 0;
    for(int i=0; i<N; i++) ans = max(ans, dp[0][i]+dp[1][i]-1);
    cout << ans;
}

 

위에서 먼저 해결한 두 문제의 풀이를 활용하여 특정 인덱스를 기준으로 그 왼쪽으로 가장 긴 증가하는 부분 수열을 구하고, 오른쪽으로는 가장 긴 감소하는 부분 수열을 구한 뒤 그 길이의 합 - 1을 구해주면 답이 됩니다.

모든 인덱스에 대해 연산을 해보아야 하므로 반복문을 여러 번 돌려주어야 합니다.

 

 

 

풀이를 제출해보면 위와 같은 기록으로 모든 테스트케이스를 통과할 수 있습니다.