newton08   3달 전

음... 예를 들어서

N=10000이고

M>9999일 때

A[0]=A[1]=.....=A[9998]=1 이고

A[9999]>M 이면

아래의 코드로는 시간초과가 나와야 하는데 그런 케이스는 없는 것 같습니다!!



시간복잡도 O(N^2) 에서 break를 통해 시간을 줄여보려고 한 코드인데

break가 나오지 않는 case에서는 시간초과가 나와야할 것 같습니다!

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

해당 코드 입니다.

#include<stdio.h>

 int main(){
    int i,j,N,M,A[10000],t,s=0;
    scanf("%d%d",&N,&M);
    for(i=0;i<N;i++)scanf("%d",&A[i]);
    for(i=0;i<N;i++){
        t=0; // t=0으로 시작해서
        for(j=i;j<N;j++){ // i번째부터 N-1까지 하나씩 더해가며 t에 누적
            t+=A[j];
            if(t==M){s++;break;} // t가 M과 같거나 커지면 break!
            if(t>M)break;
        }
        if(t<M)break;
    }
    printf("%d",s);
}

baekjoon   3달 전

추가했지만, N^2ㅇㅣ더라도 시간 초과는 나지 않습니다

newton08   3달 전

시간초과가 나는지 여부도 여쭤보려고 했었는데..

바로 알려주셨네요

감사합니다 !!

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