자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.

[실행 예]

input n: 15
output: 3 8

[설명]

15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.

* 조건 *

  1. n의 범위는 1 이상, 10000 이하입니다.
  2. 테스트 입력은 다음과 같습니다.
    20! = 2432902008176640000
    30! = 265252859812191058636308480000000
    40! = 815915283247897734345611269596115894272000000000
    50! = 30414093201713378043612608166064768844377641568960512000000000000
    100! = 93326215443944152681699238856266700490715968264381621468592963
    8952175999932299156089414639761565182862536979208272237582511852
    10916864000000000000000000000000
  3. 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다.
  4.  정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요.
  5. (심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^


먼저 정답

(calc-fact 2012)=> [501 8] (calc-fact 10000) => [2499 8]


풀이 및 코드

곱셈의 경우 상위 자리 수가 하위 자리로 내려오는 일은 없다. 고로 하위 자리만 기억하고 있으면 된다.

팩토리얼은 과거의 누적 값 * 현재 값 이다. 이때 오버플로우가 나지 않도록 누적 값에 바운더리를 적절하게 조절해 준다.

;; clojure 

(defmacro find-bound [n] `(apply * (repeat (count (str ~n)) 10)))

(defn but-last-zero [_n] (loop [n _n, zero-cnt 0] (cond (zero? (mod n 10)) (recur (int (/ n 10)) (inc zero-cnt)) :else [n, zero-cnt]))) (defn calc-fact [n] (let [[zero-cnt last-num & _] (reduce (fn [acc i] (let [[prev-zero-cnt, prev-num & _] acc, [cur-num, cur-zero-cnt & _] (but-last-zero (* prev-num i)) bound (find-bound i)] [(+ prev-zero-cnt cur-zero-cnt ), (mod cur-num bound)] )) [0 1] (range 2 (inc n)))] [zero-cnt, (mod last-num 10)]))



      분류없음  |  2012.09.07 00:59
2013.07.21 10:32 댓글에 댓글수정/삭제
귀를 기울여봐 가슴이 뛰는 소리가 들리면 네가 사랑하는 그 사람 널 사랑하고 있는거야.
.
ghd
2013.07.21 12:25 댓글에 댓글수정/삭제
희미한 달빛이 샘물 위에 떠있으면,나는 너를 생각한다.
.
2013.07.21 13:09 댓글에 댓글수정/삭제
좋으면 좋고 싫으면 싫은 거지, 뭐가 이렇게 어렵고 복잡하냐구
.
GHd
2013.07.24 04:22 댓글에 댓글수정/삭제
태양이 바다에 미광을 비추면,나는 너를 생각한다.
.
2013.07.25 03:33 댓글에 댓글수정/삭제
지금은 반짝반짝 빛이 나겠지,, 하지만 시간이 흐르면 그빛은 사라저버릴거야,지금 우리처럼
.
name ::   password :: blog :: secret
등록



blueiur's Blog is powered by Daum