BOJ 11583 - 인경호의 징검다리
DP로 풀 수 있다.
2와 5의 개수를 각 수마다 세둔다.
를 가 가장 적게 에 도달할 때 개수라고 한다면 에 모두 채울 수 있다.
이제 한 번 더 동일하게 를 가 가장 적게 에 도달할 수 있는 의 개수라고 하고 돌려준다.
그럼 정답은 임을 알 수 있다.
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;
}
Comments