인프런 커뮤니티 질문&답변

안녕하세요 대기업님 ㅎㅎ

이거 접근법부터 틀렸습니다.

문제를 볼까요?

N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다

즉, 10만 * 10만 정도의 시간복잡도를 가진 코드를 작성하셨습니다.

	for (int i = 0; i < n; i++) {
		if (i + k - 1 > n) break;
		sum = accumulate(&a[i], &a[i]+k, 0);

지금 보시는 것처럼 계속해서 k번 계산하기 때문에 n * k의 시간복잡도를 가지는 코드가 됩니다.

prefix sum 이용해서 다시 짜주세요.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.