글 읽기 - [C++]25%에서 시간초과를 벗어나지 못합니다 ㅠㅠ

uvzone 3년 전 0

분할정복, 세그먼트 트리 방식을 활용해서 풀었습니다.

처음에는 재귀 함수로 구성했다가 런타임 에러가 뜨길래 재귀함수를 사용하는 대신 큐를 활용한 반복문으로 재구성해서 나름 최소화했습니다. 그럼에도 계속 시간초과에서 벗어나질 못하고 있습니다... ㅠㅠ 어떻게 해야 더 최소화 시킬수 있을까요.. 계속 찾아보고 있는데도 해결이 안되네요 무엇이 문제일까요?ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>

#define H_LIMIT 1000000001

using namespace std;

typedef long long ull;

ull find_max_area(vector<ull> &height, int input_start, int input_end)
{
    ull max_area, min_h, temp;
    queue<int> value_q;
    int min_idx, start, end;

    start = input_start; // 부분 구간의 시작점
    end = input_end;     // 부분 구간의 종점
    value_q.push(start); // 재귀처럼 실행이 되도록 큐를 만들어 값들을 푸쉬
    value_q.push(end);

    max_area = 0;

    while (!value_q.empty())
    {
        start = value_q.front();
        value_q.pop();
        end = value_q.front();
        value_q.pop();
        min_h = H_LIMIT;
        min_idx = start;
        if (start == end) // 시작점과 종점이 같은 구간이면 너비가 1이므로 그때의 높이가 최대넓이
        {
            if (max_area < height[start])
            {
                max_area = height[start];
            }
        }
        else 
        {
            for (int i = start; i <= end; i++) // 부분 구간에서 최소높이와 그때의 index 찾기
            {
                if (min_h > height[i])
                {
                    min_h = height[i];
                    min_idx = i;
                }
            }
            if (start <= min_idx - 1) // 최소높이 index의 왼쪽부분을 재귀화
            {
                value_q.push(start);
                value_q.push(min_idx - 1);
            }
            if (min_idx + 1 <= end) // 최소높이 index의 오른쪽 부분을 재귀화
            {
                value_q.push(min_idx + 1);
                value_q.push(end);
            }
            temp = min_h * (end - start + 1); // 해당 부분 구간에서 모든 구간을 너비로하는 넓이 계산
            if (max_area < temp) // 최대 넓이값 갱신
            {
                max_area = temp;
            }
        }
    }
    return max_area;
}

int main(void)
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    vector<ull> height;
    ull input_h;
    int i, test_case, tree_length;
    do
    {
        cin >> test_case;
        if (test_case == 0)
            break;
        for (i = 0; i < test_case; i++)
        {
            cin >> input_h;
            height.push_back(input_h);
        }

        cout << find_max_area(height, 0, test_case - 1) << '\n';
        height.clear();
    } while (test_case != 0);

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++]25%에서 시간초과를 벗어나지 못합니다 ㅠㅠ

uvzone 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말