문제는 n(<3000)의 증가하는 수열이 주어질 때, 세 항 이상으로 이루어진 가장 큰 등차수열의 합을 구하는 문제입니다. 문제를 해결하고 다른 분 풀이를 보았는데 다음과 같은 풀이가 있더군요

#include<stdio.h>
int T[3000];
int C[1100000];
int main(){
    int N, i, j, k, sum, P, res=0, cnt;
    scanf("%d", &N);
    for(i=0; i<N; i++){
        scanf("%d", &T[i]);
        C[T[i]]++;
    }
    for(i=0; i<N; i++){
        for(j=i+1; j<N; j++){
            sum=cnt=0;
            for(k=T[i]; k<=T[N-1]; k+=T[j]-T[i]){
                if(!C[k]) break;
                sum+=k;
                cnt++;
            }
            if(res<sum && cnt>2) res=sum;
        }
    }

    printf("%d", res);
}

여기서 밑줄 친 부분의 시간복잡도가 최악의 경우 N^3이라고 생각해서 TLE가 날것으로 예상해 1, 2, 3 ...., 3000이라는 인풋으로 테스트를 해본 결과 예상과는 다르게 아주 빠른 시간에 해결되는 것을 확인하였습니다. 제가 시간복잡도를 잘못 계산한 건가요?

T[j] - T[i] >= j - i가 보장되므로 k는 최소 j-i씩 증가하게 됩니다.

j-i가 1이면 1씩증가, 2이면 2씩 증가, 등등

그래서 루프를 최악의 경우에도 N(N+N/2+N/3+...) = N^2(1/1+...1/N) 정도 돌아서 안전합니다

답변 감사합니다.

그렇다면 전체 시간복잡도는 O(N^2 * logN)보다 작게 되겠네요

functionx   10달 전

윗분의 설명에서 첨언하자면 1 + 1/2 + ... + 1/N이 구분구적법을 잘 사용하다 보면 O(ln N)입니다.

ln N이 log_2 N / log_2 e 이므로 O(N^2(1+...+1/N)) = O(N^2 log N)이 됩니다.

두분 모두 답변 감사합니다 ^^

kalmiaa   4달 전

저도 님 이야기듣고,

3000개 모두 등차수열인 인풋 넣어봤어요.


1. 위처럼 그냥 돌리는거

2. 숫자 i를 기준으로 A[prev_i] - A[i] 이미 탐색한것을 visited로 체크하고, 다음 방문시 체크하지 않도록 함.


백준 judge 수행시간

1. 32ms

2. 88ms -_-;

아니 뭐.. [3000][3000] 짜리 visited 함수 하나 만들고, 방문후 update 해준게 전부인데 시간이 곱절이상 늘어나네요.


3000개 등차수열.

1. 160ms 정도

2.  220ms 정도


시간은 아래와 같이 확인하였습니다.

#include<time.h>

clock_t begin, end;
 begin = clock();

end = clock();

printf("%llf\n", (double)(end - begin)  / CLOCKS_PER_SEC);


결국, 오버헤드 적은게 깡패인것 같습니다....


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