[백준] 인경호의 징검다리(11583)

문제 링크 : [백준] 인경호의 징검다리(11583)

문제 설명

n개의 징검다리가 있고, 각 징검다리에는 숫자가 있습니다.
1번 징검다리에서 시작하여 한번에 최대 k칸 건너갈 수 있는데, 징검다리를 밟을 때마다, 밟은 징검다리의 숫자를 곱해나가 마지막 징검다리를 밟았을 때 완성된 숫자들을 10^x으로 나눌수 있는 최대 x들 중 최소값을 출력하세요.

입력

t(테스트 케이스 수)
n(징검다리 갯수,2<=n<=100,000)
k(한번에 건너갈 수 있는 징검다리 갯수, 1<=k<=20)
D_i(징검다리에 쓰여진 숫자,int 범위 내)

1
8 2
5 2 2 5 10 6 2 3

출력

최소 x

2

카테고리

#DP, #소인수분해

시간 복잡도 상한

O(kn)이나 O(nlogn) 등까지 가능합니다.

해결 방법

1. 10으로 나누어지는 횟수 계산은 2와 5의 갯수 중 작은 수만큼 0이 있다고 볼 수 있습니다.
2. 1 10을 소인수분해 하면 2*5이기 때문에, 다른 수들은 0의 갯수에 영향을 주지 않고, 2와 5중 작은 수만큼 0이 생깁니다.
3. 백트래킹으로 모든 경우의 수를 계산해보면 답을 구할 수 있으나, O(n!)의 시간복잡도가 발생하기 때문에 TLE가 발생하게 됩니다.
4. 문제를 i번째 징검다리까지 올때 발생한 10의 갯수의 최소값을 구하는 부분 문제로 나눌 수 있습니다.
5. 3에서 나눈 부분 문제들을 가지고, 전체 문제를 풀 수 있습니다.
   4-1. D[i]=i번째 징검다리를 밟을 때까지 발생한 최소 10의 갯수로 정의
   4-2. D[i]=min(D[i-1],D[i-2]...D[i-k])+x(x는 i번째 징검다리에서 발생한 10의 갯수)
6. 4번처럼 문제를 풀 경우, 2와 5가 따로 발생할 경우, 카운팅이 제대로 되지 않습니다.
7. 1에서 본 것 처럼 2와 5를 따로 카운팅하여 4와 같은 점화식으로 각각 계산 한 후, 둘 중에 작은 수를 계산하면 됩니다.

시간복잡도

O(kn)

코드

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int t,n,m,d[100000],e[100020][2],i,j;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        memset(e,0,sizeof(e));
        for(i=0;i<n;i++){
            cin>>d[i];
            if(i)e[i][0]=e[i][1]=999999999;
            for(j=1;j<=m;j++){
                if(i-j<0)break;
                e[i][0]=min(e[i][0],e[i-j][0]);
                e[i][1]=min(e[i][1],e[i-j][1]);
            }
            while(!(d[i]%2))e[i][0]++,d[i]/=2;
            while(!(d[i]%5))e[i][1]++,d[i]/=5;
        }
        cout<<min(e[n-1][0],e[n-1][1])<<"\n";
    }
}