1725번 - 히스토그램
다음과 같이 작성했는데 틀렸다고 나와요.....무엇이 문제인가요?
그리고 이 문제가 스택을 활용하는 거라고 했는데 어디서 어떻게 스택을 활용해야 하는건지 모르겠어서.....힌트라도 주실수 있나요?
가장 높은 직사각형을 잡고 늘려 나가기만 하는 풀이인 듯한데, 삼각형 모양만 생각해 보아도 반례가 바로 나옵니다.
스택 풀이는 스택에 들어 있는 점의 높이들이 증가수열이 되도록 유지하고, 매 반복마다 새로 들어올 점의 높이보다 큰 값들을 빼면서 두 점으로 만드는 직사각형들만 보는 방식입니다.
쉬운 문제가 아니므로 이 설명으로 그림이 잘 그려지지 않으시면 다음에 도전하시는 것도 권장드립니다.
댓글을 작성하려면 로그인해야 합니다.
wodus0129 3년 전
다음과 같이 작성했는데 틀렸다고 나와요.....무엇이 문제인가요?
그리고 이 문제가 스택을 활용하는 거라고 했는데 어디서 어떻게 스택을 활용해야 하는건지 모르겠어서.....힌트라도 주실수 있나요?