[C++] 11054번 가장 긴 바이토닉 부분 수열 - DP

1. 문제

• 수열 S가 어떤 수 Sk를 기준으로 \(S_{1} < S_{2} < ... < S_{k} > ... > S_{N}\)을 만족할 때 이 수열을 바이토닉 수열이라고 한다.
• 수열 S가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

<입력>

• - 1 -   수열 S의 크기 N
• - 2 -   수열 S를 이루는 \(S_{i} (1 \leq N \leq 1,000, 1 \leq A_{i} \leq 1,000)\)

<출력>

• 수열 S의 부분 수열 중 가장 긴 바이토닉 수열 길이를 출력하라.

2. 재정의

• X

3. 해결 방법

• \(dp[v][0] = max(dp[i][0]) + 1, i<v\)
• \(dp[v][1] = max(dp[i][1]+1, dp[v][0]), v<i\)

4. 실수한 점, 개선할 점

• max_element를 사용할 때 dp+x하는 것보다 &dp[x]하는게 덜 헷갈린다.
• 맨 처음 시작할 때 dp 점화식 조금 더 명확하게 세우고 들어가자.

 

<코드>

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 1001;
const int MAX_V = 1001;

// <문제>
// 수열의 크기 N과 수열
int N, A[MAX_N];

// <DP>
int dp1[MAX_V], dp2[MAX_V];

void input() {
    cin >> N;
    for(int i=1; i<=N; i++)
        cin >> A[i];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    for(int i=1; i<=N; i++) {
        int v = A[i];
        dp1[v] = *max_element(&dp1[0], &dp1[v]) + 1;
        dp2[v] = max(*max_element(&dp2[v+1], dp2+MAX_N) + 1, dp1[v]);
    }
    
    cout << *max_element(dp2, dp2+MAX_N);
    
    return 0;
}

 

<max_element() 함수>

https://codechacha.com/ko/cpp-min-max-in-array/

[C++] 배열에서 최대값, 최소값 찾기 (3가지 방법)

 

<문제 바로가기>

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

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

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.