chogahui05   6년 전

저는 이렇게 풀었습니다.


(1) 롤러의 너비가 x이고, 구간 a부터 a+x-1까지 문제 조건에 맞게 칠하려면

구간 a부터 a+x-1까지의 높이 중 최솟값 만큼 칠해야 합니다.


이 특성을 생각해서 O(Llogx)에 풀었습니다.

예를 들어서 문제 데이터는 이렇게 나눴습니다.


5 3 4 중 최소 / 3 4 4 중 최소 / 4 4 5 중 최소

조금 더 빠르게 접근하려면 어떤 관점으로 접근하면 좋을까요?


최소값이 나타난 위치를 저장하면 어떨까? 라는 아이디어로도 접근하려고 했지만

case2처럼 내림차순으로 나와버리면 시간 복잡도가 O(Llogx)가 되어버리니...

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