(c++) 11054번: 가장 긴 바이토닉 부분 수열

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

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

 

 

---

 

 

문제 개요

 

 

백준 11053번의 응용문제이다.

 

11053번은 커지는 수열의 개수만 구했다면, 

11054번은 커지는 수열과 작아지는 수열을 동시에 고려해야 한다.

 

나는 각 자리에서 커지는 수열의 개수와 작아지는 수열을 각각 메모이제이션을 하고,

둘을 더해주는 형식으로 풀었다. 

 

int lis(int start) {
    int& ret = cache[start];
    if (ret != 0) return ret;
    ret = 1;
    for (int next = start+1; next < n; next++) {
        if (A[start] < A[next]) {
            ret = max(ret, lis(next) + 1);
        }
    }
    return ret;
}

 

위 코드가 11053번 해결 코드이다.

cache 배열에 저장되는 수는 각 자리부터 시작해서 커지는 수열의 길이가 저장된다.

 

입력:     1 3 2 5

배열값:  3 2 1 1

 

여기서 배열을 반대로 해서 배열을 저장하게 되면 각 자리까지의 수열의 길이가 저장된다.

 

입력:     1 3 2 5

배열값:  1 2 2 3

 

이것과 내림차순으로 저장한 배열 두 개를 이용하면

내림차순 저장 배열은 각 자리부터 작아지는 수열의 길이가 저장된다. 

 

입력:    1 3 2 5

배열값 1 2 1 1

 

두 배열에서 같은 자리 수의 합을 더하고 -1을 해주면 

바이토닉 부분 수열을 만족하는 값이 나오게 된다.

 

 

코드

 

 

#include <bits/stdc++.h>

using namespace std;

int n;
int A[1000];
// cache1 = n부터 0까지
// cache2 = 0부터 n까지
int cache1[1000], cache2[1000];
// 오름차순
int lis1(int start) {
    int& ret = cache1[start];
    if (ret != 0) return ret;
    ret = 1;
    for (int next = start-1; next >= 0; next--) {
        if (A[start] > A[next]) {
            ret = max(ret, lis1(next) + 1);
        } 
    }
    return ret;
}
// 내림차순 3 2 1 순
int lis2(int start) {
    int& ret = cache2[start];
    if (ret != 0) return ret;
    ret = 1;
    for (int next = start+1; next < n; next++) {
        if (A[start] > A[next]) {
            ret = max(ret, lis2(next) + 1);
        }
    }
    return ret;
}
int main(void) {
    cin >> n;
    for (int i=0; i < n; i++) {
        cin >> A[i];
    }
    fill_n(cache1, 1000, 0);
    fill_n(cache2, 1000, 0);
    for (int i = 0; i < n; i++) {
        lis1(n-i);
        lis2(i);
    }
    int result = 1;
    for (int i = 0; i < n; i++) {
        if (cache1[i] == 0 || cache2[i] == 0) {
            result = max(result, cache1[i] + cache2[i]);
        } else {
            result = max(result, cache1[i] + cache2[i]-1);
        }
        
    }
    cout << result;
}