[c++] BOJ 11054 :: 가장 긴 바이토닉 부분 수열

난이도 : 골드 3

걸린 시간 : 50분

문제

문제 바로가기

 

풀이

 

처음에 풀이를 이상하게 생각해서 O(n^3)의 완전탐색 혹은 DP를 사용하는 법을 생각하고 있었다. 그러다가 생각을 다시 해보니 쉽게 풀 수 있는 방법이 있어 20분만에 풀게 되었다. 역시 처음에 풀이를 주석으로 쭉 적어본 후 예제를 테스트 해보고 수행하는 것이 제일 정확하고 알맞은 방법인 듯 하다.

 

 

입력의 범위는 10^3로 그다지 높은 편은 아니었지만, 완전탐색 시 O(n^3)이 걸리므로 충분히 시간초과가 나올 수 있는 범위였다. 또한 각 숫자의 범위도 최대 10^3이므로 숫자를 하나씩 내려가며 / 올려가며 푸는 완전탐색 또한 불가능했다.

예제의 힌트를 보니 연속적이지 않은 수열의 흐름도 가능했고, 그렇다면 각 숫자가 보유하고 있는 max 값을 갱신시키는 식으로 동작하면 되지 않을까 생각했다.

• 수열이 오르는 구간을 따라가면서 가질 수 있는 max length를 저장한다.
  • ex_) 1 2 4 3 에서 3과 4는 모두 1 2 4 3 / 1 2 4 3 과 같이 3 길이의 오름차순 수열을 가질 수 있으므로 둘 다 max length가 3이다.
• 오르는 구간은 여러 경우의 수가 나올 수 있으므로 재귀함수를 이용하여 구현한다.
• 수열의 반대편에서 오르는 구간 (실제로는 내림차순 구간)을 따라가면서 max length를 저장한다.
• 두 length의 합이 max인 것을 고른 후 1을 빼준다.
  • 1 5 2 1 4 3 4 5 2 1 에서 5가 가진 length는 왼쪽에서 온 5와 오른쪽에서 온 3이다. 따라서 5 자신이 두번 카운트 되었으므로 1을 빼준 것이 정답이다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> vec; // 수열
vector<pair<int, int>> memo; // up, down

void goingUp(int start, int num, int& n) {
    for (int i = start+1; i < n; i++) {
        if (vec[start] < vec[i]) {
            if (memo[i].first < (num + 1)) {
                memo[i].first = num + 1;
                goingUp(i, num + 1, n);
            }
        }
    }
}

void goingReverse(int start, int num, int& n) {
    for (int i = start -1 ; i >= 0; i--) {
        if (vec[start] < vec[i]) {
            if (memo[i].second < (num + 1)) {
                memo[i].second = num + 1;
                goingReverse(i, num + 1, n);
            }
        }
    }
}

int main() {
     // 입력 받기
    int n; // 수열의 크기
    cin >> n;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        vec.push_back(tmp);
        memo.push_back(make_pair(0, 0));
    }

    // i를 하나씩 늘려가면서
    // 앞에서 뒤로
    // 재귀함수로 증가하면서 숫자 기록하기 (큰 걸로)
    // 반대쪽도 ㄱㄱ

    for (int i = 0; i < n; i++) {
        if (memo[i].first == 0)
            memo[i].first = 1;
        goingUp(i, 1, n);
        if (memo[i].second == 0)
            memo[i].second = 1;
        goingReverse(n-i-1, 1, n);
    }

    int max = 0;
    for (int i = 0; i < n; i++) {
        int res = memo[i].first + memo[i].second;
        if (res > max)
            max = res;
    }

    cout << max - 1;
}