boj 16161 가장 긴 증가하는 팰린드롬 부분수열

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

 

팰린드롬은 앞/뒤에서 읽었을 때 같은 수열입니다.

이 문제에서는 증가하는 팰린드롬을 구해야 합니다.

 

1, 2, 3, 4, 3, 2, 1
1, 3, 6, 7, 7, 6, 3, 1

이런것처럼 중앙으로 갈수록 값이 커지는 것이 증가하는 팰린드롬 수열입니다.

 

1, 2, 4, 3, 2, 1
4, 3, 2, 3, 4
1, 1, 1, 1

 

 

증가하는 팰린드롬이 아닌 경우는

1. 애초에 팰린드롬이 아닌 경우

2. 팰린드롬이지만 값이 증가하지 않는 경우 (값이 같아도 x)

이렇게 두가지가 되겠습니다.

 

저는 중앙을 먼저 정해놓고 한칸씩 이동하여 팰린드롬의 길이를 직접 구해봤습니다.

팰린드롬의 길이에 따라 중앙은 1개 or 2개가 될 수 있습니다.

따라서 l번째 수와 l + 1번째 수가 같으면 묶어서 중앙으로 두고 구할 수 있습니다.

이후에는 그냥 왼쪽, 오른쪽으로 한칸씩 이동하면서 증가하는 팰린드롬인지 확인해주시고, 최대 길이를 갱신해주시면 됩니다.

 

그리고 이 문제가 "증가하는 팰린드롬"이기 때문에 하나 더 생각할 수 있는건

s ~ e 범위의 팰린드롬을 찾았다고 했을 때, list[s], list[e]은 해당 팰린드롬에서 항상 가장 작은 수를 담당하고 있습니다.

그렇기 때문에 e번째 수에서 왼쪽으로 이동하더라도 큰 수가 있을 수밖에 없고, 더 큰 범위의 팰린드롬을 찾을 수 없습니다.

따라서 중앙값인 l, r을 +1씩 볼 필요 없이 s ~ e 범위의 다음 인덱스부터 다시 확인해주시면 불필요한 계산 없이 정답을 구할 수 있습니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
 
int list[MAX];
int N;
 
void func() {
    int l = 0;
    int ret = 1;
    while (l < N) {
        int r = l;
        if (r + 1 < N && list[l] == list[r + 1]) r++;
 
        int s = l - 1;
        int e = r + 1;
        while (s >= 0 && e < N) {
            if (list[s] != list[e] || list[s] >= list[s + 1]) break;
            e++;
            s--;
        }
 
        ret = max(ret, e - s - 1);
        l = e;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}