글 읽기 - 이거 왜 시간초과가 뜰까요..

cjho7356 1년 전 0

시간 복잡도도 같이 설명해주시면 감사하겠습니다.

저 생각에는 시간초과 안나게 나름대로 잘 코드 짰다고 생각했는데..

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m;
	long long a=0, ans, sum=0, now;
	cin>>n>>m;
	vector<long long>d(n);
	for(int i=0; i<n; i++){
		cin>>d[i];
	}
	for(int i=0; i<n; i++){
		a+=d[i];
		now=a;
		ans=0;
		if(a%m==0) ans++;
		for(int j=0; j<n-i-1; j++){
			now+=d[j+i+1]-d[j];
			if(now%m==0) ans++;
		}
		sum+=ans;
	}
	cout<<sum;
}

tndyd0706 1년 전 0

작성하신 코드 시간복잡도는 N^2 아닌가요?

15번, 20번 코드가 n에 대한 이중for문입니다

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

문제

문제

출처

ICPC

이거 왜 시간초과가 뜰까요..

cjho7356 1년 전 0

tndyd0706 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말