[백준 / BOJ] C++ 11054 가장 긴 바이토닉 부분 수열

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

 

문제

https://www.acmicpc.net/problem/11054

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

 

 

풀이

주어진 수열에서 점차 증가했다가 감소하는 가장 긴 부분 수열의 길이를 구하는 문제다. 아래 두 문제를 풀어본 후 도전하면 좋을 것 같다.

[11053 가장 긴 증가하는 부분 수열 문제] | [11053 가장 긴 증가하는 부분 수열 해설]

[11722 가장 긴 감소하는 부분 수열 문제] | [11722 가장 긴 감소하는 부분 수열 해설]

 

틀린 풀이 1

처음에 가장 긴 증가하는 부분 수열(이하 LIS)의 길이를 구한 후 LIS가 끝나는 위치에서 끝까지 가장 긴 감소하는 부분 수열(이하 LDS)의 길이를 구해 더한 후, LIS의 끝나는 위치와 LDS의 시작 위치가 같으므로 1 빼 출력을 하도록 했다. 하지만 제출하자마자 틀렸습니다를 받았다.

 

틀린 풀이 2

위 풀이에서 개선할 점을 찾다가 LIS가 짧고 LDS가 긴 경우가 있을 수 있다고 생각했다. 입력받은 수열의 크기가 N이라면, 0번 index부터 N-1번 index까지 탐색하는게 1번 풀이였다면, 1번 풀이로 인한 결과와 N-1번 index부터 0번 index까지 반대로 탐색한 결과를 비교해 더 큰 값을 출력해 줬다. 하지만 이마저도 제출하자마자 틀렸다.

 

맞은 풀이

마침내 찾은 반례는 질문 게시판에서 찾았다.

7

9 1 2 3 2 1 9

정답은 5인데, 2번 풀이로 실행하면 앞에서 시작하던, 뒤에서 시작하던 1 2 3 9로 답이 4가 나온다.

 

이 반례를 해결하기 위해 생각한 풀이가 LIS를 앞에서부터 구하다가 더 긴 LIS가 생길때 LIS가 끝나는 위치부터 끝까지 LDS의 길이를 구해줬다. 이 과정을 반복해 가며 생기는 길이의 최댓값을 정답으로 출력했더니 맞았다. (다행히 N 범위가 1000 밖에 안 돼서 가능한 풀이였다.)

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m = 0, ans;
  cin >> n;
  vector<int> v(n), asc(n, 1), dsc(n, 1);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++)
      if (v[i] > v[j])
        asc[i] = max(asc[i], asc[j] + 1);
    if (asc[i] > m) {
      m = asc[i];
      for (int a = i; a < n; a++)
        for (int b = i; b < a; b++)
          if (v[a] < v[b])
            dsc[a] = max(dsc[a], dsc[b] + 1);
      ans = max(ans, m + *max_element(dsc.begin(), dsc.end()) - 1);
      fill(dsc.begin(), dsc.end(), 1);
    }
  }
  cout << ans << '\n';
  return 0;
}