BOJ 24488 - Drought

June 9, 2023

만약 $n$ 이 짝수라면 모두 $0$ 으로 만드는 것의 개수를 세는것과 동일하다.

이는 $dp[i][j]$ 를 $i$ 번째 수가 $j$ 가 되고 $i$ 번째 수 이전은 모두 $0$ 인 것의 경우의 수를 세는 것이고 결국 정답은 $dp[n][0]$ 이다.

이는 단순 DP로 $O(NH^2)$ 에 세줄 수 있다.

$n$ 이 홀수라면 마지막에 어떤 레벨 $k \ k \ k\ k\dots$ 가 된다고 하자.

이는 $k \ 0 \ 0 \ 0 \dots$ 처럼 만들어줄 수 있다.

그런데 어떤 $h$ 의 조합에서 시작해서 만들 수 있는 $k$ 는 항상 고유하다. 절대 다른 $k$ 를 만들 수 없다.

따라서 모든 $k$ 에 대해 수를 세주면 $O(NH^3)$ 이 되는데, 이걸 구간합배열로 잘 최적화하면 $O(NH^2)$ 에 문제를 풀 수 있다.

You may also enjoy