Project Euler: Problem 31

Euler0031.scala

package euler.zerosum

object Euler0031 {

  val P1 = 1
  val P2 = 2
  val P5 = 5
  val P10 = 10
  val P20 = 20
  val P50 = 50
  val P100 = 100 //£1硬貨を100pとして扱う
  val P200 = 200 //£2硬貨を200pとして扱う

  val COINS = List(P1, P2, P5, P10, P20, P50, P100, P200)

  def main(args: Array[String]) {
    val amount = 200
    println(
      calcPatternsOfSplit(amount, COINS.takeWhile(_ <= amount))
    )
  }

  /**
   * 指定された種類の硬貨を用いて、指定金額を分割する方法が何通りあるかを計算する。
   *
   * @param amount
   * @param coins 利用できる硬貨のList.
   *              硬貨はその貨幣価値の昇順にソートされていること.
   * @return
   */
  private def calcPatternsOfSplit(amount: Int, coins: List[Int]): Int = {
    coins.length match {
      //使える硬貨が1pのみであれば、分割は1通りのみ
      case 1 => 1
      //使える硬貨が(1p,2p)ならば、分割は2p硬貨の最大出現数+1通り
      case 2 => amount / P2 + 1
      case _ =>
        amount match {
          case 0 => 1
          case _ => {
            coins.map(coin => {
              val diff = amount - coin
              //金額の分割は、硬貨の額面を残額から1枚分ずつ引き算することによって実現する
              //分割に使用した硬貨もしくは残額、よりも大きな貨幣価値を持つ硬貨は
              //以降の分割には使用しない。
              calcPatternsOfSplit(diff, coins.takeWhile(_ <= math.min(coin, diff)))
            }).sum
          }
        }
    }
  }
}