BOJ 24488 - Drought
만약 $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)$에 문제를 풀 수 있다.
Comments