BOJ 14587 도미노 (Large)

먼저, 주어진 배열을 $x$ 기준으로 정렬합니다. $x$가 중복이 없다는 조건이 없으므로, $x$가 같은 두 도미노가 있다면 그 중에서 $h$가 큰 것을 남깁니다.

이제 $x$는 모두 서로 다르고 오름차순으로 정렬되어 있다고 가정합니다.

이 문제는 다음과 같은 DP로 풀 수 있습니다.

• left[i]: $i$번째 도미노를 왼쪽으로 쓰러뜨렸을 때 마지막으로 쓰러지는 도미노
• right[i]: $i$번째 도미노를 오른쪽으로 쓰러뜨렸을 때 마지막으로 쓰러지는 도미노
• DP[i]: 정확히 $i$번째부터 $N$번째까지의 도미노를 쓰러뜨리는 방법들 중에서 최소 횟수

Large에서는 $N$이 크므로, left와 right를 각각 이분 탐색과 세그먼트 트리를 이용한 스위핑으로 $\mathcal{O}(N \log N)$ 시간에 구할 수 있습니다.

도미노를 정확히 $i$번째부터 $N$번째까지 쓰러뜨리려면, 크게 두 가지 방법이 있습니다.

• $i$번째 도미노를 오른쪽으로 쓰러뜨리는 경우: i + 1 이상 right[i] + 1 이하인 $j$에 대해서 1회의 동작으로 DP[j]의 상태에서 DP[i]의 상태로 들어올 수 있습니다.
• $i$번째 도미노를 왼쪽으로 쓰러뜨리는 경우: 왼쪽으로 쓰러뜨렸을 때 정확히 $i$번째까지 넘어지는, 즉 left[j] == i인 $j$에 대해서 1회의 동작으로 DP[j+1]의 상태에서 DP[i]의 상태로 들어올 수 있습니다.

첫 번째 경우는 DP를 담는 최소 세그먼트 트리의 구간 쿼리를 사용할 수 있습니다. 두 번째 경우는 그러한 $j$가 모든 $i$에 대해서 총 $N$개 존재하므로 각각 따로따로 구할 수 있습니다.