BOJ 11583 - 인경호의 징검다리

BOJ 11583 - 인경호의 징검다리

DP로 풀 수 있다.

2와 5의 개수를 각 수마다 세둔다.

$dp[i]$ 를 $2$ 가 가장 적게 $i$ 에 도달할 때 개수라고 한다면 $O(nk)$ 에 모두 채울 수 있다.

이제 한 번 더 동일하게 $dp[i]$ 를 $5$가 가장 적게 $i$ 에 도달할 수 있는 $5$의 개수라고 하고 돌려준다.

그럼 정답은 $\text{Min}(dp_2[n], dp_5[n])$ 임을 알 수 있다.

void solve() {
   int n, k;
   cin >> n >> k;
   vi two(n), five(n);
   for (int i = 0; i < n; i++) {
      int s;
      cin >> s;
      while (!(s % 2)) two[i]++, s /= 2;
      while (!(s % 5)) five[i]++, s /= 5;
   }

   int ans = 1e9;
   for (int it = 0; it < 2; it++) {
      vi dp(n, 1e9);
      dp[0] = two[0];
      for (int i = 1; i < n; i++) {
         for (int j = max(0, i - k); j <= i - 1; j++) {
            mina(dp[i], dp[j] + two[i]);
         }
      }
      mina(ans, dp[n - 1]);
      swap(two, five);
   }
   cout << ans << endl;
}