프로젝트 오일러 31

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

on Project-Euler Clojure

프로젝트 오일러 31

영국 화폐 액면가를 조합하는 방법의 수

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

재귀를 이용하면 쉽게 풀 수 있다. 동전의 종류를 숫자 1, 2, ...로 표현하면 문제를 풀 때 도움이 된다. 따라서 다음과 같이 종류 숫자를 인자로 주면 동전 값을 리턴하는 함수를 만들 수 있다.

(defn- value [n]
  (case n
    1 1
    2 2
    3 5
    4 10
    5 20
    6 50
    7 100
    8 200))

Clojure에서는 벡터를 함수로 사용할 수도 있으므로 다음과 같이 벡터를 사용해 구현할 수도 있다.

(defn- value [n]
  ([1 2 5 10 20 50 100 200] (dec n)))

벡터의 인덱스는 0부터 시작하고 동전 종류 숫자는 1부터 시작하므로, dec 함수로 인자 값을 1 감소시켰다. 동전 종류 숫자를 0부터 시작하게 할 수도 있다. 그렇게 한다면 이 함수를 호출하는 쪽에서 그에 맞게 조건을 설정하면 된다.

편의상 동전을 금액의 오름차순으로 정렬해 놓았지만, 사실 순서는 상관없다. 두 구현 모두 충분히 간단하지만, 벡터를 이용한 구현은 dec 함수를 호출하는 부분이 있어서인지 case를 사용한 구현보다 조금 느리다.

금액을 amt라고 할 때, n가지 동전을 가지고 amt를 만드는 방법은 다음 두 가짓수의 합과 같다.

  • 맨 처음 나오는 동전을 제외한 나머지 동전으로 amt를 만드는 가짓수
  • 처음 나온 동전 금액을 d라 할 때 amt - d 금액을 n가지 동전으로 만드는 가짓수

첫 번째 경우를 계산하려면 동전을 한 가지 제외하고 amt를 만드는 가짓수를 구해야 한다. 사용할 수 있는 동전은 한 가지 줄어들었지만 문제는 동일하다. 두 번째 경우는 사용할 수 있는 동전은 그대로지만 금액이 줄어든 상태에서 가짓수를 구해야 하는데, 금액만 줄었지 문제는 동일함을 알 수 있다. 즉, 첫 번째 경우나 두 번째 경우 모두 동전 가짓수나 금액만 줄어들 뿐 로직(또는 알고리즘)은 그대로 쓸 수 있다. 즉 재귀를 사용할 수 있다.

재귀를 사용할 때는 항상 규칙이 끝나는 경우를 정리해야 한다.

  • amt가 0이면 해당 금액을 만드는 방법은 1가지 밖에 없다.
  • amt가 0보다 작은 금액을 만드는 방법은 없다. (0가지)
  • n이 0이면 금액을 만드는 방법은 없다. (0가지)

이 규칙을 이용해 금액을 만드는 방법의 가짓수를 구하는 함수를 다음과 같이 만들 수 있다.

(defn- cc [amt n]
  (cond
    (= amt 0) 1
    (< amt 0) 0
    (= n 0) 0
    :else (+ (cc amt (dec n))
             (cc (- amt (value n)) n))))

문제를 다 푼 것이나 마찬가지다. (cc 200 8)을 실행하면 답을 구할 수 있다. 다른 풀이와 코드 형식을 맞추기 위해 다음과 같이 solve 함수를 만든다.

(defn solve []
  (cc 200 8))

실행 결과는 다음과 같다.

p031=> (time (solve))
"Elapsed time: 171.989327 msecs"
736??

참고