[1725]히스토그램

히스토그램 실패다국어

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

예제 입력 1 

7
2
1
4
5
1
3
3

예제 출력 1 

8

 

막무가내로 풀다가 시간초과 당해버렸다.

일단 틀린 풀이 먼저 올리고 나중에 풀어야겠다.

 

#include<iostream>
#include<vector>
int f(int *arr, int arr_size)
{
    int max = 0;
    int temp;
    for (int i = 0; i < arr_size; i++)
    {
        temp = 0;
        for (int j = 0; j < arr_size; j++)
        {
            if (arr[i] <= arr[j])
            {
                temp += arr[i]; 
            }
            else if (temp >= max)
            {
                max = temp;
                temp = 0; 
            }
            if (temp >= max && j == arr_size - 1)
            {
                max = temp;
                temp = 0;
            }
        }
    }
    return max;
}
int main()
{
    std::vector<int> sum;
    while (1)
    {
        int arr_size; std::cin >> arr_size;
        if (arr_size == 0) break;
        int* arr = new int[arr_size];
        for (int i = 0; i < arr_size; i++)
        {
            std::cin >> arr[i];
        }
        sum.push_back(f(arr, arr_size));
        delete[]arr;
    }
 
    for (int i = 0; i < sum.size(); i++)
    {
        std::cout << sum[i];
    }
}

...1 j가 배열의 끝까지 올 때까지 아래 과정을 반복

arr[i]가 arr[j]보다 작다면 temp에 arr[i]를 더한다.

arr[i]가 arr[j]보다 크다면 더하는 거 끊고 최댓값인지 판별한다.

 

...2 i가 배열의 끝에 올 때까지 ...1의 과정을 반복