[문제 링크]



Trailing zero의 최적을 구하는 문제다.

Trailing zero는 숫자에 들어있는 0의 갯수를 말하는데, 숫자에 0이 들어가려면 인수로 10을 가지고 있어야 한다.

따라서 소인수분해 시, 2와 5의 짝 만큼 Trailing zero가 추가된다.


이 문제는 소인수 2와 5를 가장 적게 가지는 경로를 찾는 문제이다.


모든 경로에 대해서 소인수 2와 5의 갯수를 전부 메모이제이션 한다.


앞서 설명한 대로 10이 만들어지려면 2와 5가 동시에 필요하므로, 2나 5중 가장 작은 값이 Trailing zero의 최소값이 된다.


지금 위치부터 K만큼 앞에 있는 징검다리를 비교하면서, 소인수 2와 5의 갯수가 최소가 되는 값을 찾아 각각 저장해나가면 구할 수 있다. 



단 주의해야 할 점은 dp를 할때 재귀(top-down)를 쓰면 시간초과가 발생한다.(연산 갯수가 총 10만개이다.)

이 문제는 반복문(bottom-up)으로풀어야 해결이 가능하다.


#include <cstdio> #include <cstring> #include <algorithm> #define MAX_VAL 987654321; int T, N, K, S[100001], cache[100001][2]; int getPf(int div,int input){ int ret = 0; while(input%div == 0){ ret++; input /=div; } return ret; } void stepping_stone(){ cache[0][0] = getPf(2,S[0]); cache[0][1] = getPf(5,S[0]); for(int cur = 1; cur<N; cur++){ cache[cur][0] = MAX_VAL; cache[cur][1] = MAX_VAL; for(int j=1;j<=K;j++){ int prev = cur-j; if(prev >= 0){ cache[cur][0] = std::min(cache[cur][0],cache[prev][0] + getPf(2,S[cur])); cache[cur][1] = std::min(cache[cur][1],cache[prev][1] + getPf(5,S[cur])); } } } printf("%d\n",std::min(cache[N-1][0],cache[N-1][1])); } int main(){ scanf("%d",&T); while(T--){ scanf("%d %d",&N,&K); for(int i = 0; i<N; i++) scanf("%d",&S[i]); stepping_stone(); } }


'Algorithm > Problems' 카테고리의 다른 글

백준 - 10215 Colored Bead Works  (0) 2016.05.25
백준 - 2800 괄호 제거  (1) 2016.05.18
알고스팟 - WEEKLYCALENDAR  (0) 2016.05.09
백준 - 10219 Meats On The Grill  (0) 2016.05.09
더블릿 - 미로찾기/starship_maze  (0) 2016.05.09

+ Recent posts