안녕하세요,
재재입니다.
BOJ 14727 퍼즐 자르기 문제에 대한 풀이입니다.
BOJ 14727 퍼즐 자르기
(1) 문제 설명
분류 : data structure, range minimum query, range maximum query, segment tree
출처 : https://www.acmicpc.net/problem/14727
(10만 이하) N개의 가로가 1인 직사각형의 높이가 주어집니다.
한 번 자를때 왼쪽 및 오른쪽으로 현재 직사각형보다 높이가,
같거나 큰 직사각형을 자를 수 있습니다.
예를들면, 직사각형의 높이를 3, 4, 5, 2 라고 했을 때
3인 직사각형에서 한 번 잘라서 얻을 수 있는 직사각형의 넓이는 3 * 3 입니다.
이때, 한 번 잘라내서 얻을 수 있는 직사각형의 최대 넓이를 구해주면 됩니다.
(2) 풀이 도출
현재의 높이를 기준으로 왼쪽 및 오른쪽에 한 번의 쿼리로,
현재 높이보다 낮은 곳의 위치를 알아야 합니다.
이는 range minimum (maximum) query 를 통해 알 수 있는데,
왼쪽에서 오른쪽으로 진행한다고 가정한다면,
현재 높이 h를 기준으로 $$ query(0, h-1) $$에서 가장 큰 값을 찾으면,
현재 인덱스 i를 기준으로 가장 가까운 곳을 알 수 있습니다.
전체 시간복잡도 $$ O(n log n) $$ 에 해결 가능합니다.
BOJ 14727 퍼즐 자르기