글 읽기 - 6549번 시간복잡도 계산 관련해서 질문 드립니다.

juice500 8년 전 0

문제를 접근할 당시 Divide & Conquer 방식으로 중간에 있는 원소를 포함하는 경우를 계산하고 아닌 경우를 해당 원소 왼쪽과 오른쪽 구간으로 분할하여 푸는 방식을 택했습니다.

중간에 있는 원소를 포함한 정답을 계산하는 함수가 msum(), 분할하여 비교하는 함수가 tsum()입니다.

소스코드에서 msum()함수의 시간복잡도가 O(n)이고, tsum()함수의 시간복잡도는 O(n*log₂(n))인 것 같은데 왜 시간초과가 나는지 모르겠습니다.

흐.. 아무리 봐도 잘 모르겠네요 엉엉 불쌍한 중생을 구원해주세요ㅠ_ㅜ

#include<stdio.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
int num[100000],tmp[100000];
long long int msum(int l,int m,int h) {
    long long int i,j,ans = num[m];
    tmp[m] = num[m];
    for(i=m-1;i>=l;--i)
        tmp[i] = min(tmp[i+1],num[i]);
    for(i=m+1;i<=h;++i)
        tmp[i] = min(tmp[i-1],num[i]);
     
    i=m-1;
    j=m+1;
    while(i>=l||j<=h) {
        if(j>h || tmp[i]>tmp[j]) {
            ans = max(ans,(j-i)*tmp[i]);
            i--;
        }
        else if(i<l || tmp[i]<=tmp[j]) {
            ans = max(ans,(j-i)*tmp[j]);
            ++j;
        }
    }
    return ans;
}
long long int tsum(int l,int h) {
    if(l==h) return num[l];
    int m = (l+h)/2;
    long long int lt = tsum(l,m), ht = tsum(m+1,h), mt = msum(l,m,h);
    return max(lt,max(ht,mt));
}
int main(void) {
    int n,i;
    while(1) {
        scanf("%d",&n);
        if(!n) return 0;
        for(i=0;i<n;++i) scanf("%d",num+i);
        printf("%lld\n",tsum(0,n-1));
    }
    return 0;
}

juice500 8년 전 0

흐.. 그렇군요 감사합니다

juice500 8년 전 0

주신 테스트케이스를 돌려보니 이리저리 고쳐봐도 20초정도 걸리는 것 같습니다

아무래도 이 방법은 아닌가봅니다ㅜ_ㅠ 감사합니다

juice500 8년 전 0

우와 감사합니다!!!! 저래서 시간초과였다니!

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

문제

문제

출처

ICPC

6549번 시간복잡도 계산 관련해서 질문 드립니다.

juice500 8년 전 0

juice500 8년 전 0

juice500 8년 전 0

juice500 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말