[구현] 백준 16161 :: 가장 긴 증가하는 팰린드롬 부분수열

가장 긴 증가하는 팰린드롬 부분수열 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1.5 초	512 MB	179	66	58	41.429%

문제

팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드롬이 아니다.

증가하는 팰린드롬 수열이란 원소들이 바깥에서 팰린드롬 중심으로 갈 수록 값이 증가하는 팰린드롬 수열을 말한다. 수열 {1, 2, 3, 2, 1}, {32, 59, 75, 75, 59, 32}는 증가하는 팰린드롬이고, {3, 2, 1, 2, 3}, {32, 57, 57, 80, 57, 57, 32}, {8, 7, 9, 7, 8}은 증가하는 팰린드롬이 아니다.

주어지는 수열 S에서 인접한 원소들로 구성된 부분수열 중 길이가 가장 긴 증가하는 팰린드롬 부분수열의 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 S의 길이 N(1 ≤ N ≤ 105)이 주어진다.

둘째 줄에 수열 S의 i번째 원소를 의미하는 정수 Si(1 ≤ Si ≤ 109)가 순서대로 공백으로 구분되어 주어진다.

출력

수열 S에서 인접한 원소들로 구성된 부분수열 중 길이가 가장 긴 증가하는 팰린드롬 부분수열의 길이를 출력하라.

예제 입력 1 

10
1 3 1 5 7 7 5 7 7 5

예제 출력 1 

4

     

 문제 풀이

1차 풀이 (  2884 KB,  20 ms)

별 다른 알고리즘 없이,  구현에 착실하면 해결할 수 있다.

N이 큰것같지만, 올바르게만 구현하면 항상 O(N)정도로 풀림.

원소가 같은 중앙을 고른 뒤, 양 옆으로 확장한다.

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

int N, val;
vector<int> A;

//! 팰린드롬의 길이를 구한다.
//! 첫 실행시, A[left]==A[right]가 보장되어야 함.
int palindrome(int left, int right){
        int len  = (left==right? 1 : 2);
        int prev = A[left];
        int s = left;
        int e = right;
        while(true){
                s--;
                e++;
                if(s==-1 || e==N || A[s]!=A[e] || prev<=A[s]) break;
                len+=2;

                //! 다음 요소는 더 작아야 함.
                prev = A[s];
        }
        return len;
}


int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        //! data input.
        cin >> N;
        for(int i=0; i<N; i++) {
                cin >> val;
                A.emplace_back(val);
        }
        A.push_back(0); // 마지막에는 dummy data 하나를 삽입.


        //! 정답의 크기는 항상 1보다 같거나 큼.
        int ans = 1;
        for(int i=0; i<N; i++){
                ans = max(ans, palindrome(i, i));
                if(A[i] == A[i+1]) ans = max(ans, palindrome(i, i+1));
        }
        cout << ans;
}