[알고리즘] Algospot_FENCE

출처 : https://www.algospot.com/judge/problem/read/FENCE

문제

너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다.

판자의 너비는 모두 1이라고 가정합니다.

입력

첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.

출력

각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.

정답코드

#include<bits/stdc++.h>
#define endl '\n'

int n,hi;

using namespace std;

int hihi(vector<int>& v, int pos, int hight)
{
    if(pos==n)  return 0;
    if(v[pos+1]<hight)    return 1;

    return 1+hihi(v,pos+1,hight);
}

int main()
{
    int t;

    cin >> t;

    while(t--)
    {
        cin >> n;

        vector<int> v(n,0);
        vector<int> total(n,0);

        for(int i=0; i<n; i++)
            cin >> v[i];

        for(int i=0; i<n; i++)
        {
            total[i]+=hihi(v,i,v[i])*v[i];
        }
        
        reverse(v.begin(), v.end());

        for(int i=0; i<n; i++)
        {
            total[n-i-1]+=v[i]*hihi(v,i,v[i])-v[i];
        }

        int max=0;
        for(int i=0; i<n; i++)
            if(max<total[i])    max=total[i];

        

        cout << max << endl;
    }

    
    return 0;
}

풀이 및 사고과정

책에서 지향하는 분할정복 대신에 다른 방법을 풀어보았다.
사실 분할 정복을 하려하였으나 재귀를 다루는 것에 익숙하지않아 다른 방법을 이용했다.
c++자체가 빠른 언어에 속해서 시간초과에 걸리지 않고 해결하였다.
이 코드는 1300ms이 걸렸다.
책에서는 1000ms가 제한이고 풀이 사이트에는 3000ms가 제한이기 때문에 정답이 가능했던 것이다. 따라서 이 문제는 책을 참고한 뒤 분할 정복으로 다시 한 번 코드를 작성할 예정이다.