BOJ 14586 도미노 (Small)

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

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

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

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

Small에서는 $N$이 작으므로 left와 right를 모두 나이브로 구할 수 있습니다.

도미노를 정확히 $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]의 상태로 들어올 수 있습니다.

이들을 모두 나이브하게 계산하면 $\mathcal{O}(N^2)$의 시간에 문제를 풀 수 있습니다.