글 읽기 - [C언어] 2559번 질문 있습니다.

sae4394 1년 전 0

슬라이딩 윈도우 알고리즘을 알기 전에 이렇게 풀면 되겠다 싶어서 한번 풀어봤습니다.
각 수를 받을 때마다 미리 짜놓은 result 배열에 수를 += 해주면 입력받을 때마다 바로 계산이 되니까 O(n)으로 입력은 끝난다고 생각해서 했는데
시간 초과가 뜨더라고요. 이게 마지막 qsort 때문에 시간 초과가 뜨는 걸 까요? 아니면 입력할 때 추가로 생기는 문제가 있을까요?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int array[1000001] = { 0, };

int cmp(const void* A, const void* B) {
	return (*(int*)A - *(int*)(B));
}

int main() {

	int N, M;
	scanf("%d %d", &N, &M);

	int* result = (int*)calloc(N - M + 2, sizeof(int));

	for (int i = 1; i <= N; i++) {
		int temp;
		scanf("%d", &temp);

		if (i < M) {
			for (int j = 1; j <= i; j++) {
				result[j - 1] += temp;
			}
		}
		else if (i >= M && i <= N - M + 1) {
			for (int j = i - M + 1; j <= i; j++) {
				result[j - 1] += temp;
			}
		}
		else {
			for (int j = i - M + 1; j <= N - M + 1; j++) {
				result[j - 1] += temp;
			}
		}


	}
	qsort(result, N - M + 1, sizeof(int), cmp);

	printf("%d", result[N - M]);

}

zenith82114 1년 전 1

i 루프 안에 j 루프로 이중 반복문이 있는 시점에서 이미 O(N)이 아닙니다.

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

문제

문제

출처

ICPC

[C언어] 2559번 질문 있습니다.

sae4394 1년 전 0

zenith82114 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말