BOJ 11583 - 인경호의 징검다리

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

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

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 1006 - 습격자 초라기

문제 : https://www.acmicpc.net/problem/1006 DP[i][j] : i 번째 열, j타입일 때 남은 열을 적절히 놓아서 만들 수 있는 최소 침투 소대수라고 정의하고 다이나믹 프로그래밍으로 풀면 된다. 이 문제에서 까다로운 점은 구역이 원형으로 연결돼 있다는 점인데, 이는 처음과 끝에 이미 몇개의 소대를 보내 놨다고 생각 (이러면 선형구조로 생각할 수 있음) 하고, 그 경우에 대해 모두 돌려보면 된다. 길이 N에 처음과 끝을 가정하는 경우의 수는 상수번 이므로 O(N)에 풀린다. 코드 : http://ideone.com/XPpr2X 비슷한 문제 (이 문제를 푸는데 동원된 아이디어와 비슷한) : https://www.acmicpc.net/problem/9465 https://www.acmicpc.net/problem/2133 https://www.acmicpc.net/problem/2482 https://www.acmicpc.net/problem/4017
계속 읽기