히스토그램에서 가장 큰 직사각형

처음으로 푸는 플레티넘단계의 문제이다

접근

이문제는 분할정복으로 분류되어있다

따라서 분할해서 풀수있는방법이 있는지 먼저 생각해보았다

하지만 분할정복을 이용한 마땅한 해법이 떠오르지않았고

 

오히려 반대로 동적개획법 개념을 이용하여 풀수있을만한 방법이 떠올랐다

 

동적계획법

# 히스토그램에서 가장 큰 직사각형

# 입력받기
while True:
    a=list(map(int,input().split()))
    if a==[0]:
        break
    d=[0]*100000
    
    for i in range(1,a[0]+1):
        max_value=a[i]
        for j in range(i+1,a[0]+1):
            new=min(a[i:j+1])*len(a[i:j+1])
            if new>max_value:
                max_value=new
            else:
                break
        
        d[i]=max_value
    print(max(d))

맞았으면 코드에 관한 상세설명을 하려했지만 20%즈음해서 시간초과가 났다 하하

이것보다 더 효율적인 방법이 있나보다 역시!

빨리풀고 밥도 먹으러 가고 싶은데 말이다

 

분할정복의로서의 접근

Q. 분할을한다면 어느쪽으로 세로로 나누는게 좋을까? 아니면 가로로 나누는게 좋을까?

A. 이것의 답은 정해져있는것같다 h의 범위가 0에서 10억까지이기때문에 무조건 세로로 나눠야 한다

 

Q. 분할을 한다면 언젠가 결국 합쳐야 되는데 어떻게 할것인가?

이문제에대한 해결책을 찾지못했다 그렇다 분할후 블럭을 조립하듯이 점점 더 큰 직사각형을 찾는방식을 생각했지만

쉽게 예외의경우를 찾을수있었다 문제없이 돌아가는방식은 위의 시간초과난 방법밖에 없었다

 

해답을보고 공부해보자

몇시간고민했고 끝내 지쳤다 

https://www.youtube.com/watch?v=v4OX1OTzma4&ab_channel=IOIKOREA 

해당강의를통해 개념을 잡았고 전체적인 풀이과정을 아래 포스트를 보고 이해했다

https://hooongs.tistory.com/330

[백준6549번] 히스토그램에서 가장 큰 직사각형 / Python3

 

느낀점

개념을 어느정도 이해하고 코드작성을했다 이것도 새벽이라 졸렸는지 잔에러도 발생해서 빨리끝내진못했다

오늘 하루종일 이문제만 붙들고있으면서 시간을보냈음에도 불구하고 아직도 완전히 이해한것같지는않아서

찜찜하다 어쨋든 여차저차 풀었고 앞으로도 ps를 게을리하지말아야겠다는 생각이들었다