프로젝트 오일러 99

내 이 세상 도처에서 쉴 곳을 찾아보았으나, 마침내 찾아낸, 컴퓨터가 있는 구석방보다 나은 곳은 없더라.

프로젝트 오일러 99

밑과 지수 형태로 나타낸 수 중 가장 큰 수 찾기

문제 자세히 보기: [국어] [영어]

로그 개념을 알면 쉬운 문제다. 큰 수에 \log 를 취하면 작은 수로 바꿀 수 있다. 예를 들어 10^{100} 은 1 뒤에 0이 백개나 붙는 큰 수지만 \log_{10} 10^{100} 은 그냥 100이다. 그러나 \log 는 단조증가 함수기 때문에 어떤 수 x y 보다 크다면 \log x \log y 보다 크다.

%math \begin{aligned} x^a &\gt y^b \newline \log x^a &\gt \log y^b \newline a \log x &\gt b \log y \end{aligned}

또한 \log x^a 는 간단히 a \log x 로 바꿔 쓸 수 있다. a \log x 를 구하는 것은 쉬운 일이다. 파일에서 읽어들인 밑과 지수를 각각 b (base)와 e (exponent)라 하면 e \log b 를 계산해 가장 큰 수를 찾으면 문제를 풀 수 있다.

이를 Clojure로 구현하면 다음과 같다. 여기서는 밑이 10인 상용로그를 사용했지만 자연로그를 써도 결과는 같다.

(ns p099
  (:require [util :refer [parse-int]]
            [clojure.string :refer [split]]))

(def log-vals
  (->> (split (slurp "data/base_exp.txt") #"\r\n")
       (map (fn [s] (split s #",")))
       (map (fn [[b e]] [(parse-int b) (parse-int e)]))
       (map (fn [[b e]] (* e (Math/log10 b))))
       (map-indexed vector)))

가장 큰 수가 몇 번째인 지 구하는 것이 문제이므로 계산한 값과 인덱스를 묶어서 시퀀스로 만들어 두었다. 가장 큰 숫자가 몇 번째인지는 다음 코드로 구할 수 있다. 위에서 인덱스를 0부터 시작했으므로 구한 값에 1을 더해야 답이 된다.

(defn solve []
  (+ 1 (first (apply max-key (fn [[i v]] v) log-vals))))

실행 결과는 다음과 같다. 빠르게 답을 구한다.

p099=> (time (solve))
"Elapsed time: 0.218719 msecs"
7?9

참고