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

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

---

문제)

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

 

입력 :

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

 

 

 

 

출력 :

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

 

 

 

 

풀이)

 

Top-down 풀이

// 11054. 가장 긴 바이토닉 부분 수열
#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
vector<int> vec;
 
int dp[1010][1010][2];
 
int recur(int cur, int prev, int drt)
{
    int ret = 0;
 
    if (cur == n) return 0;
 
    if (dp[cur][prev][drt] != -1)
    {
        return dp[cur][prev][drt];
    }
 
    if (drt == 0 && vec[cur] > prev)
    {
        ret = max(ret, recur(cur + 1, vec[cur], 0) + 1);
        ret = max(ret, recur(cur + 1, vec[cur], 1) + 1);
    }
    else if (drt == 1 && vec[cur] < prev)
    {
        ret = max(ret, recur(cur + 1, vec[cur], 1) + 1);
    }
    ret = max(ret, recur(cur + 1, prev, drt));
 
    dp[cur][prev][drt] = ret;
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
 
    fill(&dp[0][0][0], &dp[1009][1009][2], -1);
    vec.resize(n);
    for (auto& ele : vec) cin >> ele;
 
    cout << recur(0, 0, 0);
 
    return 0;
}
 

 

 

bottom-up 풀이

 

// 11054. 가장 긴 바이토닉 부분 수열
#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
vector<int> vec;
 
int dp[1010][2];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    vec.resize(n);
    for (auto& ele : vec) cin >> ele;
 
    int ans = 0;
    
    dp[0][0] = 1;
    dp[0][1] = 1;
 
    for (int i = 1; i < n; i++)
    {
        dp[i][0] = 1;
        dp[i][1] = 1;
 
        for (int j = i - 1; j >= 0; j--)
        {
            if (vec[j] < vec[i])
            {
                dp[i][0] = max(dp[i][0], dp[j][0] + 1);
            }
            else if (vec[j] > vec[i])
            {
                dp[i][1] = max(dp[i][1], max(dp[j][1] + 1, dp[j][0] + 1));
            }
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        ans = max(ans, max(dp[i][0], dp[i][1]));
    }
 
    cout << ans;
 
    return 0;
}
 

---

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

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