朝日新聞2006年1月6日のパズル横丁問題

問題

1円玉，5円玉，10円玉，50円玉，100円玉，500円玉の6種類全てを使い合計18枚で2006円にする。

但し，100円玉は2枚使用する。

解答への道(ヒント)

新年一発目の問題。今年は正月休みが短かったせいか，正月用特別編成のパズルが無かったようだ。

6種類の硬貨を1枚ずつ使わなければならないので，一つの種類について最高13枚使う可能性がある。

ということは，単純に以下のようなループを作れば良い。

  for( int i500=1; i500< 13; i500++) {
    for( int i100=1; i100< 13; i100++) {
      for( int i50=1; i50< 13; i50++) {
        for( int i10=1; i10< 13; i10++) {
          for( int i5=1; i5< 13; i5++) {
            for( int i1=1; i1< 13; i1++) {
              18枚で2006円になったら発見。
            }
          }
        }
      }
    }
  }

これだと解が4つ出力されてしまう。100円玉は2個使用するという条件を以下のようにする。

for( int i100=2; i100< 3; i100++) 

13⁵(≒100万)回のループになる。大したことは無いので，途中

if( i500*500+i100*100+i50*50+i10*10+i5*5 > 2006) break;

というような文を入れる必要もない(最初入れて作った)。

解は1件出力されました。

今年一年が楽しくプログラミングできる良い年でありますように。

解速度

即