川添さん問題09 ディビジョン・ナイン

■■■問題■■■

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) の値を出力するプログラムを書いてください。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("1");
            //0
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            //10
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4");
            //40
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("20");
            //最悪計算量
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int n = int.Parse(InputList[0]);

        //場合の数[9を法とした余り]なDP表
        const int UB = 9 - 1;
        long[] PrevDP = new long[UB + 1];
        PrevDP[0] = 1;

        for (int I = 1; I <= n; I++) {
            long[] CurrDP = new long[UB + 1];

            for (int J = 0; J <= UB; J++) {
                if (PrevDP[J] == 0) continue;
                for (int K = 1; K <= 4; K++) {
                    int NewJ = (J + K) % 9;
                    CurrDP[NewJ] += PrevDP[J];
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[0]);
    }
}

解説

動的計画法で解いてます。

「ディビジョン・ナイン」問題解説 --- CodeIQ MAGAZINE