【paiza×Qiita】お菓子の詰め合わせ (paizaランク A 相当)  C#編

## はじめに

「会社で業務の傍ら採用のお手伝いをしているけど、あんまり募集進んでない・・・いいアピールの方法ないかな？」
 と思っていたところ、日頃お世話になっているQiitaで面白そうなキャンペーンを見つけて、
 
 「これ使えないかな？」
 と試験的に投稿してみることにしました。所属企業を公開されてる方たちもいるしね。
 ~~決してApple Watchがほしいわけではありません。うん。~~


問題を見てみて、「ハノイの塔がAかー、このくらいのランクならなんとか解けそうかな？」
ということで、チャレンジしてみました。言語はC#です。
それではどうぞ。


## お菓子の詰め合わせ（初回提出)

#### 考え方
条件は以下3つ。
・商品は種類ごとに1つしか買うことはできない
・与えられた金額でできるだけ多くの商品を買うこと
・商品の個数が同じであれば、できるだけおつりが少なくなるように買うこと

解法は以下のように考えた。
1. 商品を安い順から買えるだけ買う ( = できるだけ多くの商品を買うことが可能)
1. 買った商品とそれ以外のより高い商品を比較し、差額が予算内に納まれば商品を交換する( = できるだけ高い商品を買い、おつりを少なくする）

#### ソースコード
	using System;
	using System.Collections.Generic;
	using System.Linq;

	class Program
	{
	    static void Main()
	    {
	        // 1行目(種類, 総額)の取得
	        var line1 = Console.ReadLine().Split(' ');
	        var kind = int.Parse(line1[0]);
	        var amount = int.Parse(line1[1]);
	        
	        // 2行目以降(商品)の取得
	        var products = new List<int>();
	        for (int ii = 0; ii < kind; ++ii)
	        {
	            products.Add(int.Parse(Console.ReadLine()));
	        }
	        
	        // 昇順ソート必須
	        products.Sort();
	        
	        //最少額の商品から限界まで購入する(購入可能な種類数を求める) 
	        var boughtList = new List<int>();
	        foreach (var product in products)
	        {
	            if ((boughtList.Sum() + product) > amount) { break; }
	            boughtList.Add(product);
	        }

	        // 購入した商品から、残金の範囲でできるだけ高い金額の商品と交換する
	        for (int ii = 0; ii < boughtList.Count; ++ii)
	        {
	            var preOrder = -1;
	            foreach (var product in products)
	            {
	                // すでに購入していた商品は除く
	                if (boughtList.Contains(product)) { continue; }
	                // 購入した商品より高額、かつ総額の範囲に納まる商品を探す
	                if ( (product > boughtList[ii]) &&
	                     (boughtList.Sum() + (product - boughtList[ii]) <= amount) )
	                {
	                    // 交換可能な商品を仮押さえしておき、差額の大きい商品があれば更新する
	                    preOrder = product;
	                }
	            }
	            // できるだけ差額の大きい商品と交換する
	            if (preOrder >= 0) { boughtList[ii] = preOrder; }
	        }
	        
	        // 購入した商品の残額を出力する
	        Console.WriteLine(amount - boughtList.Sum());
	    }
	}

## 結果（初回提出)
foreachしてるコレクションをループ中に変更するなんてダメだろ、とコンパイラ様にマサカリを投げられる恐怖を抱えつつ、まあ通ったしええやろの精神で提出。
~~赤点の予感を感じつつテストを提出した気分でした。~~

結果は・・・

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3679685/383af35f-7c1c-e98d-252e-4803513585c3.png)

思ったよりいい。
1パターン通らなかったらしく、しっくりこないので確認する

## 気づき
「これ結局、総当たり必要じゃね？」
そう、最もお釣りの少なくなる組み合わせが欲しいのであって、それは必ずしも高い商品ではないのだ。（とても高い商品と安い商品のパターンもあれば、すべてそこそこ高い商品のパターンもある）
ひとつずつ交換していたのでは正しい答えは得られない。

「いい考えだと思ったのになぁ」とうなだれつつ、コードを修正する。~~まるで現実のようだ~~

## 最終提出
解法1. の「商品を安い順から買えるだけ買う」の部分に関しては正しいはずなので、商品の個数は求められた前提でコードを修正した。

#### ソースコード
	using System;
	using System.Collections.Generic;
	using System.Linq;
	class Program
	{
	    static void Main()
	    {
	        // 1行目(種類, 総額)の取得
	        var line1 = Console.ReadLine().Split(' ');
	        var kind = int.Parse(line1[0]);
	        var amount = int.Parse(line1[1]);
	
	        // 2行目以降(商品)の取得
	        var products = new List<int>();
	        for (int ii = 0; ii < kind; ++ii)
	        {
	            products.Add(int.Parse(Console.ReadLine()));
	        }
	
	        // 昇順ソート必須
	        products.Sort();
	
	        //最少額の商品から限界まで購入する(購入可能な種類数を求める) 
	        var boughtList = new List<int>();
	        foreach (var product in products)
	        {
	            if ((boughtList.Sum() + product) > amount) { break; }
	            boughtList.Add(product);
	        }
	
            // 修正部分
	        var productCount = boughtList.Count;
	        boughtList.Clear();

	        var sum = ChoiseProducts(products, productCount, amount);
	
	        // 購入した商品の残額を出力する
	        Console.WriteLine(amount - sum);
	    }
	
        // 再帰関数を追加
	    public static int ChoiseProducts(List<int> productList, int productCount, int amount, int oldSum = 0, int sum = 0)
	    {
	        --productCount;
	
	        foreach (var product in productList)
	        {
	            // 商品を買う
	            sum += product;
	
	            // 最大個数の商品を買うまで繰り返す
	            if (productCount > 0)
	            {
	                // 購入した商品を除いて他の商品をチョイスする
	                var copyProductList = new List<int>(productList);
	                copyProductList.Remove(product);
	                oldSum = ChoiseProducts(copyProductList, productCount, amount, oldSum, sum);
	            }
	
	            // よりお釣りの少ない組み合わせが見つかったら合計を更新する
	            if ((productCount == 0) && (sum <= amount) && (sum > oldSum))
	            {
	                oldSum = sum;
	            }
	            sum -= product;
	        }
	
	        return oldSum;
	    }
	}

なんか、コレジャナイ感。。。
うまぶって再帰関数にしたけれどわかりにくい。あとコレクションのコピーが重い。
~~そもそも早さを求める人はC#は使わないだろうが~~

まぁ愚直に作るとN次の繰り返しになるので仕方ないね。次元を減らさない限り。
なにはともあれ、100点をいただくことができました。やったぜ。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3679685/5bb0748f-abb6-5cf1-78cd-a2520b008fd2.png)

## おわりに
ちょっと時間がかかってしまいましたが、解くことができました。
頭のトレーニングにはちょうどいいですね。

次はオブジェクト指向的にモデリングしてみても面白いかも。。なんて。
以上です。

 **※初投稿のため、気になった点・マサカリがあれば教えていただけると幸いです。**