글 읽기 - 시간 초과 나는데 어떻게 고쳐야할지 모르겠습니다.

dbsgur6896 3년 전 0

분할정복을 사용했는데 O(nlogn) 효율이 안나는 것일까요?

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair < ll, ll>;
using matrix = vector<vector<ll>>;

const int Max_N = 1e6 + 1;
const int mod = 1e9 + 7;

ll n, a[Max_N];
ll mx = 0;

void merge(int x, ll n) {
    
    int cnt = 0;
    ll tmp = 0;
    tmp = n % 2 ? tmp + n / 2 : tmp + 1 + n / 2;
    ll h = a[tmp];
    for(int i = tmp; i < x + n; i++) {
        if (h > a[i]) break;
        cnt++;
    }
    for(int i = tmp - 1; i >= x; i--) {
        if (h > a[i]) break;
        cnt++;
    }

    mx = max(mx, cnt * h);
}

int dc(int x, ll n) {
    
    if (n == 1) {
        mx = max(mx, a[x]);    
        return x;
    }
    else {
        if (n % 2 == 1) {
            dc(x, n / 2 + 1);
            dc(x + n / 2 + 1, n / 2);
            merge(x, n);
        }
        else {
            dc(x, n / 2);
            dc(x + n / 2, n / 2);
            merge(x, n);
        }
    }
    return x;
}


int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    while (true) {
        cin >> n;
        if (n == 0)break;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        dc(0, n);
        cout << mx << "\n";
    }
    return 0;
}

byeongkeunahn 3년 전 0

시간 초과가 난 이유는 20번째 줄이 잘못되었기 때문입니다. tmp가 0으로 초기화되어있기 때문에 x가 큰 경우 아래의 for loop가 너무 오래 돌게 되어 시간 초과가 나는 것입니다.

하지만 해당 부분을 수정해도 맞지 않습니다. 분할 정복에서 고려하는 케이스가 tmp를 반드시 포함하는 것은 맞지만, 반드시 tmp의 높이 전체를 사용하는 것은 아닙니다. 예를 들어 높이가 99, 100, 101로만 구성된 Fence 100개가 무작위로 나열된 경우 tmp의 높이가 101이라면 실제 답은 모든 Fence 100개를 다 사용하는 것이겠지만 현재 로직으로는 tmp의 높이보다 작은 것을 만나는 순간 종료하므로 틀립니다.

분할 정복을 사용하는 것 자체는 맞으니 다시 생각해 보시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

시간 초과 나는데 어떻게 고쳐야할지 모르겠습니다.

dbsgur6896 3년 전 0

byeongkeunahn 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말