글 읽기 - 다음코드가 왜 통과되는지 궁금합니다.

7slidemorning 4년 전 0

우선, O(1억) 이 1초 정도에 돌아간다고 가정하겠습니다.

이중 for 문으로 모든경우를 탐색하기 때문에 시간복잡도 O(n^2) 로,

N = 10000 일때 아래의 코드는 O(1억) 의 시간복잡도로 실행된다고 생각하는데

시간제한이 0.5초인 이문제에 대해서 아래의 코드가 왜 통과가 되는지 궁금합니다.

p.s 첫번째 코드는 두번째 코드에서 가지치기를 한것인데

첫번째 40ms

두번째 52ms 에 통과가 됩니다.

//////////////////////////////////// 첫번째 ////////////////////////////////////
#include <cstdio>

long long a[10001];

int main(void){
    int n, m;
    int ans = 0;
    scanf("%d %d", &n, &m);
    
    for(int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
        if(a[i] == m) ans++;
        a[i] += a[i-1];    
    }

    for(int i=1; i<=n-1; i++){
        if(a[i]-a[i-1] > m) continue;
        for(int j=i+1; j<=n; j++){
            if(a[j]-a[i-1] > m) break;
            else if(a[j]-a[i-1] == m) ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}
///////////////////////////////////////////////////////////////////////////////


//////////////////////////////////// 두번째 ////////////////////////////////////
#include <cstdio>

long long a[10001];

int main(void){
    int n, m;
    int ans = 0;
    scanf("%d %d", &n, &m);
    
    for(int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
        a[i] += a[i-1];    
    }

    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            if(a[j]-a[i-1] == m) ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}
///////////////////////////////////////////////////////////////////////////////

kimyul528 4년 전 2

서버와 컴퓨터 성능 등에 따라 약간식 다를 수도 있지만 대략 c++ 는 1초에 4억번 (또는 그 이상) 정도 연산을 합니다.

그래서 O(n^2) 를 돌리면 1억번 연산을 하게 되고, 1초에 2억번연산만 넘지 않으면 되니 통과를 하게 됩니다.

참고로 제가 알고 있는 정보가 틀릴 수도 있습니다;;

djm03178 4년 전 1

요즘 컴퓨터는 단순한 문장 루프는 10억~20억번도 돌립니다.

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

문제

문제

출처

ICPC

다음코드가 왜 통과되는지 궁금합니다.

7slidemorning 4년 전 0

kimyul528 4년 전 2

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말