글 읽기 - 14727번 질문드립니다.

wlsth1004100 5년 전 0

코드 요약을하자면 높이값이 담긴 배열을 한바퀴돌면서 현재높이 만들수있는 최고의 직사각형 합을구하고

max값을 갱신시키는 순서로 코드를 짜봣으나 98퍼에서 시간초과가 뜨게됩니다 ㅠㅠ 그리하여 불필요한 연산을 줄이기위해 고민하던중

sum = 현재의 높이 if (sum*n <= max) break; 이코드를 추가하여 어차피 max값이 안될거라면 불필요한 연산을 하지않겠음 코드를 써보았으나

제출해보니 틀렸다고 뜨네요.. 제머리속에선 이코드가 안될 반례가 도저히 떠오르지가않는데 왜틀리는지 알려주셨으면 좋겠습니다..!

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

int main()
{
	int i, n, *arr, sum, max = 0;
	int left_flag, right_flag, left, right;
	scanf("%d", &n);
	arr = (int*)malloc(sizeof(int)*n);

	for (i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	for (i = 0; i < n; i++)
	{
		left_flag = 1;
		right_flag = 1;
		left = i - 1;
		right = i + 1;
		sum = arr[i];
		while (1)
		{
			if (sum*n <= max)
				break;
			if (left < 0 || (arr[left] < arr[i]))
				left_flag = 0;
			if (right >= n || (arr[right] < arr[i]))
				right_flag = 0;
			if (left_flag) {
				sum += arr[i];
				left--;
			}
			if (right_flag) {
				sum += arr[i];
				right++;
			}
			if (!left_flag && !right_flag)
				break;
		}
		if (sum > max)
			max = sum;
	}
	printf("%d", max);
	return 0;
}

djm03178 5년 전 1

정확한 알고리즘은 모르겠으나, sum과 n이 적당히 큰 수라면 둘을 곱했을 때 int의 범위를 벗어날 듯 합니다.

wlsth1004100 5년 전 0

sum과 n을 long long int 로바꾸니 해결됬습니다 감사합니다!

djm03178 5년 전 0

하지만 이 코드는 여전히 최악의 경우 O(N^2)이라 통과되면 안 됩니다. 데이터가 약한 것 같아 추가를 요청했습니다.

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

문제

문제

출처

ICPC

14727번 질문드립니다.

wlsth1004100 5년 전 0

djm03178 5년 전 1

wlsth1004100 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말