2905번 - 홍준이와 울타리
저는 이렇게 풀었습니다.
(1) 롤러의 너비가 x이고, 구간 a부터 a+x-1까지 문제 조건에 맞게 칠하려면
구간 a부터 a+x-1까지의 높이 중 최솟값 만큼 칠해야 합니다.
이 특성을 생각해서 O(Llogx)에 풀었습니다.
예를 들어서 문제 데이터는 이렇게 나눴습니다.
5 3 4 중 최소 / 3 4 4 중 최소 / 4 4 5 중 최소
조금 더 빠르게 접근하려면 어떤 관점으로 접근하면 좋을까요?
최소값이 나타난 위치를 저장하면 어떨까? 라는 아이디어로도 접근하려고 했지만
case2처럼 내림차순으로 나와버리면 시간 복잡도가 O(Llogx)가 되어버리니...
댓글을 작성하려면 로그인해야 합니다.
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)가 되어버리니...