[PS/Clojure] HackerRand - Algorithms - Construct the Array

DP 를 사용하는 Sherlock and CostConstruct the Array

오랜만에 아무 힌트없이 풀었다 크흠...

Construct the Array | HackerRank

Lee-WonJun/ProblemSolving

(defn exp [x n]
  (reduce * (repeat n x)))

(def mod-value (+ 7 (exp 10 9)))
(defn my-mod [x] (mod x mod-value))

(defn tail-count [d-avail d-number-one d-answer acc k n]
    (let [avail (my-mod (* k d-avail))
          number-one (my-mod (- d-avail d-number-one))
          answer (my-mod (- avail number-one))]
          (if (= acc n) d-answer
          (recur avail number-one answer (inc acc) k n))))

(defn count-dp [n k x]
    (let [n-n (- n 2)
          n-k (dec k)
          n-o (if (= x 1) 1 0)]
          (tail-count 1 n-o 1 0 n-k n-n)))

 

보다 효율적으로 풀기위하여 1~~~X 가 아닌 X~~~1 식으로 생각하면서

이전의 가능한 경우의수 - 이전의 가능한 1의 개수를 빼면 된다.