📝 문제 정보#
문제#
Barbara는 정원을 가지고 있다. 정원은 길고 좁으며, 일렬로 배치된 $m$개의 동일한 크기의 구역으로 나뉘어 있다. 그녀의 친구 Babara는 생일 선물로 $n$개의 디딤돌을 주었다. Barbara는 이 디딤돌들을 정원에 배치하여 매일 디딤돌을 밟으며 즐길 수 있게 했다. $i$번째 디딤돌은 정원의 $l_i$번째부터 $r_i$번째 구역을 완전히 차지한다. 디딤돌들은 서로 겹치지 않으며, 어떤 두 디딤돌 사이에도 최소 $d$개의 빈 구역이 있다.
아래는 $m = 15$, $n = 3$, $d = 2$이고, 세 디딤돌이 각각 $2$–$4$번, $7$–$7$번, $12$–$13$번 구역을 차지하는 유효한 배치의 예시이다.
Barbara는 최근 정원의 $x$개의 연속된 구역을 차지하게 될 디딤돌을 하나 새로 구입했다. 그녀는 기존 디딤돌들을 정원 안에서 이동시킨 후, 새 디딤돌을 정원 어딘가에 놓을 것이다. 기존 디딤돌들을 이동시키고 새 디딤돌을 놓은 후, 디딤돌들은 서로 겹치지 않아야 하며 어떤 두 디딤돌 사이에도 최소 $d$개의 빈 구역이 있어야 한다. 또한 디딤돌을 재배치하는 과정에서도 디딤돌들은 서로 겹치지 않아야 한다.
디딤돌 하나를 인접한 구역으로 이동시키는 데 1분이 걸린다. 예를 들어, 위의 재배치 과정은 4분이 걸린다. 이제 Barbara는 “다른 목적"을 위해 시간을 아낄 수 있도록, 디딤돌들을 재배치하여 새 디딤돌을 정원에 놓을 수 있게 하는 데 필요한 최소 총 시간을 알고 싶다.
입력#
첫째 줄에 네 정수 $n$, $m$, $d$, $x$가 주어진다. 다음 $n$줄의 $i$번째 줄에는 두 정수 $l_i$와 $r_i$가 주어진다.
출력#
새 디딤돌을 정원에 놓을 수 있도록 디딤돌들을 재배치하는 데 필요한 최소 총 시간(분)을 출력한다. 아무리 재배치해도 새 디딤돌을 정원에 놓을 수 없다면 -1을 출력한다.
🧐 관찰 및 접근#
- 흠, 일단 -1이 나오는 상황은 그리디하게 가능한 것 같다.
- 맨앞으로 다 밀었다고 생각하고, 들어가나 안들어가나?를 보면 되겠네.
- 그 다음에는, 결국 잘 밀고싶을 뿐이다.
- 새로운 디딤돌이 들어갈 위치를 고정한다음에 나머지를 구해볼까?
- 하지만, 그렇게 하기에는 시간복잡도가 $m$에 붙으면, 터져버린다.
- $n$에 붙게 해야할 것 같은데.. 그러면 디딤돌이 $k, k+1$번째 사이에 들어간다고 가정하자. 이때 $O(n)$에 최솟값을 구할 수 있다면, $O(n^2)$에 문제를 해결할 수 있을 것 같다. 로그 하나정도도 붙어도 될 것 같고.
- 일단 예시 1번을 이용해보자.
- $(2-4), (7-7)$ 두개의 디딤돌 사이에 들어가려고 한다.
- 맨 왼쪽으로 붙었다면 $(1-3), (6-8), (11-11), (14-15)$ 처럼 완성되어야 할 것 같다.
- $(6-8)$이 새로 들어온 디딤돌이다.
- 어? 이거 $m$에 대해 삼분탐색으로 구할 수 있지 않을까?
- 그렇게하고 그리디하게 $n$번 돌면서 밀면서 체크하면 $O(n^2\log{m})$에 풀릴 것 같은데
💻 풀이#
- 코드 (C++):