글 읽기 - 어디서 틀리는건지 반례좀 부탁드립니다..

gowithmylord 7년 전 0

경우를 2가지로 나눴는데요.

i번째 히스토그램 막대를 입력받을 때,

res[i-1].max엔 i-1번째 막대로 만들 수 있는 최대 직사각형 넓이가 저장되있고,

res[i-1].height는 그 직사각형의 높이가 저장되있습니다.

그래서

res[i-1].height와 현재 받은 i번째 막대를 비교해서,

i번째 막대가 더 높은 경우엔, i-1번째까지 만든 최대 직사각형을 한칸 더 늘리는 것이 가능하므로,

변의 길이 = 넓이/높이로 구해서 +1한다음 늘린 직사각형의 크기와 i번째 막대 자체의 크기와

비교해서 더 큰 값을 저장합니다.

반대로 i번째 막대가 작은 경우, i번째 막대의 높이로 생성할 수 있는 직사각형의 최대 크기를 구하기 위해,

for문을 돌려서 i번째 막대보다 작은 막대를 만나기전까지 밑변의 길이를 구해냅니다.

그렇게 구한 직사각형의 크기와 i번째 막대의 높이를 저장합니다.

이 두가지로만 보면, i번째마다 가질 수 있는 최대 직사각형 크기를 구해나가는 것이라고 생각이 되는데,

반례가 있는건가요?.. 글이 길어진 듯하여 죄송합니다. 이해가 안되시는 부분은 코드를 참조해주시면 감사하겠습니다.

#include<iostream>
#define max(a,b) (((a)>(b))?(a):(b))

typedef struct{
	int max;
	int height;
}block;

int main(){
	int n,*data,ans,pos;
	block* res;
	int i,j;
	scanf("%d",&n);
	data = (int*)malloc(sizeof(int)*n);
	res = (block*)malloc(sizeof(block)*n);
	for(i=0;i<n;i++){
		scanf("%d",&data[i]);
		pos = 0;//밑변의 길이를 저장하는 변수
		if(i==0){
			res[i].height = res[i].max = data[i];
			ans = data[i];//최대 크기를 저장하는 변수
			continue;
		}
		if(res[i-1].height > data[i]){
			for(j=i;j>=0;j--){
				if(data[j] < data[i])
					break;
				pos++;
			}//밑변의 최대 길이를 구한다
			pos = pos*data[i];
			res[i].max = pos;
			res[i].height = data[i];
			if(res[i].max > ans)
				ans = res[i].max;
		}
		else{
			if(data[i] == 0){
				res[i].max = res[i].height = 0;
				continue;
			}
			pos = res[i-1].max/res[i-1].height;
			pos = (pos+1)*res[i-1].height;//밑변의 길이를 한칸 더 늘린 직사각형
			res[i].max = max(data[i],pos);
			if(res[i].max == data[i])
				res[i].height = data[i];
			else
				res[i].height = res[i-1].height;//높이 값 갱신
			if(res[i].max > ans)
				ans = res[i].max;
		}
	}
	printf("%d",ans);
		
}

gallopsys 7년 전 1

8

1 2 3 4 5 6 7 8

라는 테스트 케이스가 주어지면 20(가로 = 4, 세로 = 5 혹은 가로 = 5, 세로 4)이 나와야하는데, 14가 나오네요..

gowithmylord 7년 전 0

아...미처 생각치 못한 오류가 많네요 생각보다...ㅠ
아예 새로 짜야겠습니다... 문제에서 분류해준대로 스택을 이용해봐야겠네요... 감사합니다

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