BOJ 11583 - 인경호의 징검다리

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

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

댓글

댓글 쓰기

이 블로그의 인기 게시물

repeated squaring

https://www.acmicpc.net/problem/1533 최대 가중치 5인데 한 정점을 정점 다섯개로 치환하고 모든 간선의 가중치가 1인것처럼 만든다. 그런식으로 만든 인접행렬을 거듭제곱하면 답을 구할 수 있다. http://codeforces.com/problemset/problem/621/E
계속 읽기

인덱스트리(Indexed Tree)

어떤 구간의 최대,최소를 O(lgN)에 알게 해주는 자료구조  정의되는 연산 1.) 원소값 갱신 2.) a~b의 최대 또는 최소값 반환 완전이진트리를 배열로 구현  ( 들어갈 원소 숫자만큼의 단말노드를 가질 수 있도록 크기를 조정 , 편의상 그냥 4 * N으로 잡으면 된다. 값은 단말노드를 통해서만 들어간다.                예 : 들어갈 원소가 9개라고 한다면 최소한 단말노드가 9개                      여야 하므로 비단말노드 15개, 단말노드 16개를 가지는                      완전이진트리 형태가 되어야 할것이다.  ) 원소값 갱신: 원소가 하나 추가될때마다 부모노드와 비교하여 최대, 최소 ( 또는 다른 그 구간을 대표할만한)을 갱신한다. a~b의 최대,최소 반환: a (왼쪽끝 노드)에 있는 노드가 오른쪽노드일때 그 부모노드가 구간을 대표하는 값을 가질 수 없다는점을 이용하여 노드의 위치가 오른쪽일때는 그 오른쪽에 에 위치하는 왼쪽노드  (이 두 노드는 서로 다른 부모노드를 가진다.) 로, 왼쪽노드일때는 부모노드로 위치를 옮겨가면서 리턴값을 갱신한다. 반대로 b(오른쪽끝 노드) 노드는 왼쪽노드일때 그 노드의 왼쪽에 있는 오른쪽노드, 오른쪽 노드일때 그 부모노드로 위치를 옮겨가면서 리턴값을 갱신한다. 두 위치가 교차되거나 겹칠때 루프를 종료한다. const int INF = 2e9 ; struct Tree { int first; vector<int> tree; Tree (int n) { for...
계속 읽기