경우를 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번째마다 가질 수 있는 최대 직사각형 크기를 구해나가는 것이라고 생각이 되는데,

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


gallopsys   3달 전

8

1 2 3 4 5 6 7 8

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

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

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