ディビジョン・ナイン
問題概要
1 から 4 の数字を使って n 桁の整数を作ります。このとき、9 の倍数となるものを考えましょう。
例えば n = 3 であれば、234、333、441、などが 9 の倍数です。必ずしも 1 から 4 の全ての数字を使う必要はありません。
1 から 4 の数字を使って作る n 桁の整数のうち、9 の倍数となるものの個数を F(n) と定義します。
例えば、F(1) = F(2) = 0、F(3) = 10、F(4) = 40 となることが確かめられます。
標準入力から、自然数 n(1 ≦ n ≦ 20)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。
解法
桁で表すことができる値 を書き出していけば以下のようにパスカルの三角形みたいになる。
桁で値 を表す個数は、(1桁目を1として(n-1)桁で(m-1)を表す個数)+(1桁目を2として(n-1)桁で(m-2)を表す個数)+・・・(1桁目を4として(n-1)桁で(m-4)を表す個数)であるので、
value[桁][値] = value[桁 - 1][値 - 1] + value[桁 - 1][値 - 2] + value[桁 - 1][値 - 3] + value[桁 - 1][値 - 4]
である。
Python3によるコード
n = int(input()) l = [[0 for i in range(4*n + 1)] for j in range(n + 1)] # l[桁数][値] l[1][1] = l[1][2] = l[1][3] = l[1][4] = 1 count = 0 for i in range(2, 4*n+1): for j in range(2, n + 1): l[j][i] = sum(l[j - 1][i - 4 if i - 4 >= 0 else 0:i]) if i % 9 == 0 and j == n: count += l[j][i] print(count)
このコードはnが大きくなるとメモリ効率が悪い。
私のコードでは、ある値 から までの5つの値を 桁ぶん覚えていればよいので、最低限必要な配列は でよい。