ARC-001-B リモコン

■■■問題■■■

高橋君は、エアコンの設定温度を変更しようとしています。
現在の設定温度はA度ですが、これをB度に設定したいと思っています。
エアコンのリモコンは1回ボタンを押すことで、

● 1度設定温度を下げる、もしくは上げる
● 5度設定温度を下げる、もしくは上げる
●10度設定温度を下げる、もしくは上げる
の、6種類の操作のいずれか 1 つを実行することが出来ます。
高橋君が設定温度をA度からB度に変更するために押すボタンの最小回数を求めなさい。

■■■入力■■■

A B

●1行目は現在の設定温度を表す整数 A (0 <= A <= 40) と、
  設定したい温度を表す整数 B (0 <= B <= 40) が与えられる。

■■■出力■■■

高橋君がボタンを押す必要のある回数の最小値を1行に出力せよ。 

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("7 34");
            //5
            //10度、10度、5度、1度、1度の順で上げていくと、5回で設定することが出来ます
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("19 28");
            //2
            //10度上げた後に、1度下げることで、2回で設定することが出来ます
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 10");
            //0
            //同じ温度の時は、設定温度を変える必要はありません
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int a = wkArr[0], b = wkArr[1];

        //遷移可否[温度]なDP表
        bool[] DPArr = new bool[40 + 1];
        DPArr[a] = true;

        int UB = DPArr.GetUpperBound(0);
        int ChangeCnt = 0;
        while (DPArr[b] == false) {
            var NewIndList = new List<int>();
            foreach (int EachHeni in new int[] { -10, -5, -1, 1, 5, 10 }) {
                for (int I = 0; I <= UB; I++) {
                    if (DPArr[I] == false) continue;
                    int NewInd = I + EachHeni;
                    if (NewInd < 0 || UB < NewInd) continue;
                    NewIndList.Add(NewInd);
                }
            }
            NewIndList.ForEach(X => DPArr[X] = true);
            ChangeCnt++;
        }
        Console.WriteLine("{0}", ChangeCnt);
    }
}

解説

動的計画法で遷移可能な温度を管理してます。