글 읽기 - 12846 시간초과 질문드립니다 . C

dltmdwo0508 4년 전 0

저는 배열을 받아서 내림차순으로 바꾼뒤에 그 배열에 숫자가 변하는 구간을 체크하여

구간마다의 합을 구해 가장 큰 수를 구했습니다.

하지만 fot while문이 많이 들어가서 시간초과가 나오는대

더 똑똑한 방법으로 푸신 분 있을까요?? 시간을 줄이려면 어떻게 해야될까요 ㅜㅜ

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

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main()
{
	int i, j, N, o = 0;

	scanf("%d", &N);

	int *arr, *sum, *number;

	arr = (int*)malloc(sizeof(int)*N);
	sum = (int*)malloc(sizeof(int)*N);
	number = (int*)malloc(sizeof(int)*N);

	int p = 0;

	for (i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
		sum[i] = -1;
		number[i] = -1;
	}

	int tmp;

	for (i = 0; i < N; i++)//내림차순으로 배열 
	{
		for (j = i; j < N; j++)
		{
			if (arr[i] < arr[j])
			{
				swap(&arr[i], &arr[j]);
			}
		}
	}

	o = 0, p = 0;
	number[p] = arr[0];
	p++;

	for (i = 0; i < N - 1; i++)
	{
		if (arr[i] > arr[i + 1])
		{
			sum[o] = i;//배열 수가 변하는 구간 
			number[p] = arr[i + 1];//그 구간의 숫자
			o++; p++;
		}
	}

	int max = 0, check = 0;
	p = 0, o = 0;

	while (sum[o] != -1)
	{
		for (i = 0; i <= sum[o]; i++)
		{
			check += number[p];
		}
		if (max < check)
		{
			max = check;
		}
		p++, check = 0, o++;
	}

	for (i = 0; i < N; i++)
	{
		check += number[p];
	}

	if (max < check)
		printf("%d\n", check);
	else
		printf("%d\n", max);

	free(arr);
	free(sum);
	free(number);

	return 0;
}

sait2000 4년 전 1

이 문제랑 똑같은 문제니까 읽어보시면 어떨까요

https://www.acmicpc.net/blog/v...

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

문제

문제

출처

ICPC

12846 시간초과 질문드립니다 . C

dltmdwo0508 4년 전 0

sait2000 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말