Q20 受難のファサードの魔方陣

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int[] NumArr ={ 1,14,14, 4,
                       11, 7, 6, 9,
                        8,10,10, 5,
                       13, 2, 3,15};

        //場合の数[和]なDP表
        var DPDict = new Dictionary<int, int>();
        DPDict[0] = 1;
        foreach (int EachNum in NumArr) {
            foreach (int EachKey in DPDict.Keys.OrderByDescending(X => X)) {
                int wkSumVal = EachKey + EachNum;
                if (DPDict.ContainsKey(wkSumVal))
                    DPDict[wkSumVal] += DPDict[EachKey];
                else DPDict[wkSumVal] = DPDict[EachKey];
            }
        }
        foreach (var EachPair in DPDict.OrderBy(X => X.Value).ThenBy(X => X.Key)) {
            Console.WriteLine("和が{0}になる組み合わせは{1}通り", EachPair.Key, EachPair.Value);
        }
    }
}

実行結果

省略
和が69になる組み合わせは1350通り
和が64になる組み合わせは1357通り
和が68になる組み合わせは1357通り
和が65になる組み合わせは1361通り
和が67になる組み合わせは1361通り
和が66になる組み合わせは1364通り

解説

場合の数を更新する動的計画法で解いてます。