[백준] 11054번 : 가장 긴 바이토닉 부분 수열

문제

 

---

풀이

 

myunji.tistory.com/214

[백준] 11053번 : 가장 긴 증가하는 부분 수열

이 문제를 응용한 문제이다.

 

11053번이 왼쪽->오른쪽으로 탐색하며 수열의 길이를 구했다면

이번에는 i에 대해 왼쪽->오른쪽으로도 탐색하고 오른쪽->왼쪽으로도 탐색해야 한다.

---

소스코드

 

#include <iostream>
using namespace std;

struct bi_arr { //l은 왼쪽부터 오름차순, r은 오른쪽부터 오름차순
    int value, l_point, r_point;
};
bi_arr* arr = new bi_arr[1001];
int dp[1001] = { 0, };
int point = 1;

void cal(int index, int* dp, int flag) { //11053과 같음
    for (int i = point; i >= 0; i--) {
        if (arr[index].value > dp[i]) {
            dp[i + 1] = arr[index].value;
            if (flag == 0)
                arr[index].l_point = i + 1;
            else
                arr[index].r_point = i + 1;
            if (i == point)
                point++;
            return;
        }
    }
}

int bitonic(int num) {
    dp[1] = arr[1].value;
    arr[1].l_point = 1;
    for (int i = 2; i <= num; i++) { //왼쪽부터 순회
        cal(i, dp, 0);
    }
    point = 1; //dp 포인터 초기화

    dp[1] = arr[num].value;
    arr[num].r_point = 1;
    for (int i = num - 1; i >= 1; i--) { //오른쪽부터 순회
        cal(i, dp, 1);
    }

    int max = 0;
    for (int i = 1; i <= num; i++) { //max값 찾기
        if (arr[i].l_point + arr[i].r_point > max)
            max = arr[i].l_point + arr[i].r_point;
    }
    return max - 1; //1개 중복 계산되니까 1빼기
}

int main() {
    int N;

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> arr[i].value;
    cout << bitonic(N);
}

전체 소스코드다.

 

struct bi_arr { //l은 왼쪽부터 오름차순, r은 오른쪽부터 오름차순
    int value, l_point, r_point;
};

i번째 수에 대해 증가 수열의 길이는 l_point에 저장하고, 감소 수열의 길이는 r_point에 저장할 것이다.

 

void cal(int index, int* dp, int flag) { //11053과 같음
    for (int i = point; i >= 0; i--) {
        if (arr[index].value > dp[i]) {
            dp[i + 1] = arr[index].value;
            if (flag == 0)
                arr[index].l_point = i + 1;
            else
                arr[index].r_point = i + 1;
            if (i == point)
                point++;
            return;
        }
    }
}

11053번에서 사용한 코드와 거의 유사하다.

다만 이번에 구할 것은 전체 길이가 아니라 index에 대한 증감 길이이기 때문에 arr[index].value > dp[i]를 발견하면 바로 i+1를 반환한다.

 

    dp[1] = arr[1].value;
    arr[1].l_point = 1;
    for (int i = 2; i <= num; i++) { //왼쪽부터 순회
        cal(i, dp, 0);
    }
    point = 1; //dp 포인터 초기화

bitonic 함수에선 왼쪽->오른쪽으로 이동하며 증가 수열을 먼저 구한다.

그리고나서 감소 수열을 구하기 전 dp의 길이를 나타내는 point 변수를 1로 초기화 해서 다시 사용할 수 있도록 한다.

 

    dp[1] = arr[num].value;
    arr[num].r_point = 1;
    for (int i = num - 1; i >= 1; i--) { //오른쪽부터 순회
        cal(i, dp, 1);
    }

감소 수열을 구할 때는 오른쪽->왼쪽으로 이동한다.

이렇게 하면 똑같이 증가 수열을 찾는 것처럼 보이기 때문에 cal 함수를 재활용 할 수 있다.

 

    int max = 0;
    for (int i = 1; i <= num; i++) { //max값 찾기
        if (arr[i].l_point + arr[i].r_point > max)
            max = arr[i].l_point + arr[i].r_point;
    }
    return max - 1; //1개 중복 계산되니까 1빼기

마지막으로 arr의 모든 수에 대해 l_point와 r_point를 더한 값을 계산해 가장 긴 바이토닉 부분 수열의 길이를 찾는다.

각각의 l_point와 r_point에는 자기 자신이 1번씩 총 2번 들어가기 때문에 1을 빼준다.