BOJ 11583 - 인경호의 징검다리

https://www.acmicpc.net/problem/11583

trailling zero를 최소화 한다는 것은 그 수를 소인수분해 했을때 2와 5의 지수 중 작은 것을 최소화 하는 것과 같다. 2의 지수만을 보고 구한 것과 5의 지수만을 보고 구한 것 중 작은 값이 답이 된다. 이것은 다이나믹 프로그래밍으로 쉽게 구할 수 있다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 2401 - 최대 문자열 붙여넣기

문제 :  https://www.acmicpc.net/problem/2401 각각의 짧은 문자열들이 긴 문자열에서 어디에 등장하는지만 알 수 있다면, 이 문제는 전형적인 다이나믹 프로그래밍 문제가 된다. 그러니깐 KMP를 돌리면서 테이블을 채우면 된다. 시간 복잡도는 긴 문자열 길이 $S$, 짧은 문자열 길이 $T$, 짧은 문자열의 수 $N$이라 할때 $O(N * (S + T))$가 된다. 코드 :  http://ideone.com/zloOUb
계속 읽기

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n
계속 읽기