1000円渡されたら何種類の切手を買えるのか？
ことのほったん（と思われるの）は以下のツイートから
そしてこういう考えを思いついた人もいた（伝え方が完全に悪かったのだけど、）インターンの大学生に1,000円分の切手を買ってきてとお願いしたら、1,000円切手1枚を渡された……。
— 大木 一真｜モジカクしごと (@ooki_kazuma) 2019年6月10日
聞いたら、そもそも切手を買ったことなんて今までなかったそう。これが令和……。 pic.twitter.com/FxZrEIJiy0
「1000円分の切手を買ってきて」と言われたときの買い方が何パターンあるかはプログラミングの練習問題に良さそうだ、と試しにやってみたら再帰計算しすぎて死んだ
— 柞刈湯葉（いすかりゆば） (@yubais) 2019年6月11日
以下ここに書かれることは筆者の自己満足と自分の考えが正しいかがよくわからないため他人による評価を（ちょびっとだけ）もらいたいために書かれた記事であることを先に言っておく。
タイトルにもある通り「1000円で何種類の切手を買えるか」とあるがここでは「N円で何種類買えるか」という問題にしておく。
日本郵便さんによると切手は
1円、2円、3円、5円、10円、・・・、500円、1000円とあるそうだ。 www.post.japanpost.jp
この問題をDP問題として、次にPythonで書いたものを示す。
kinds = [1,2,3,5,10,20,30,50,62,82,92,100,120,140,205,280,310,500,1000] dp = [1] N = 10 for i in range(1,N+1): s = [dp[i-j] for j in kinds if i-j>=0] print(s) dp.append(sum(s)) print(i,"円の時",dp[i],"通り。")
まずは考え方から、この問題を0円からスタートし1円を買うには切手のうちどれを使い1円未満の値段での買い方から選ぶという方針でやっている。
上のコードを出力すると
[1] 1 円の時 1 通り。 [1, 1] 2 円の時 2 通り。 [2, 1, 1] 3 円の時 4 通り。 [4, 2, 1] 4 円の時 7 通り。 [7, 4, 2, 1] 5 円の時 14 通り。 [14, 7, 4, 1] 6 円の時 26 通り。 [26, 14, 7, 2] 7 円の時 49 通り。 [49, 26, 14, 4] 8 円の時 93 通り。 [93, 49, 26, 7] 9 円の時 175 通り。 [175, 93, 49, 14, 1] 10 円の時 332 通り。
となり、配列sを出力することで思い通りに計算されてるかを確認することができる。例えば10円渡されて買うとき
残り1円切手で10円ぶんになる切手の種類から残り10円切手で10円ぶんになる切手の種類までを足せばいい
つまり、最後に買う切手を[1円切手、2円切手、3円切手、5円切手、10円切手]と考えたとき、この配列は
切手の種類が[9円のとき、8円のとき、7円のとき、5円のとき、0円のとき]と考えることができる。これらの種類を足せば10円渡されて買える切手の種類が出せる、と私は考えた。
おまちかね、1000円のときだが、上のNを1000にしたときの出力が
1000 円の時 2018816696222847406903248298783095971003454597950956950486814286870151769566638334351695889582461204439244633372769436724665312005396075530178629791204098410261766867285766690432361030106623128263952566362440060615017667935586334548238897367080748492851021980966669336418640390 通り。
恐ろしい数が出てしまって正直自分の考えがあってるとは思えなくなってしまった。
追伸：僕なら1000円渡されたら50円切手を20枚買うね。
追記(2019/06/12)
上の計算の仕方には問題点があった。
たとえば、3円渡された時を考える。
上のコードでは「1円切手、2円切手」と「2円切手、1円切手」を別々に計算している点だ。これでは切手の買う種類が爆上がりするのも納得いく。
まだ思いつかないけどね
