【C言語】お金の個数の組み合わせ【備忘録】

お札N枚でぴったりY円が作れるか判定する

AtCoderで解いていた問題（とその修正）の自分用メモです。

問題：
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。

（AtCoderより引用）

最初に立てた方針：
　一万円が0～n枚の場合を考える
　五千円が0～n枚の場合を考える
　千円が0～n枚の場合を考える
　ただし五千円および千円はより大きい金額のお札と合わせてn枚を超えない範囲のみ考慮する
　以上を入れ子状のループにし、合計金額がY円と一致するか組み合わせごとに判定する

ぴったりN枚でY円になる場合のみが条件に合致する

問題の条件を読めば、x+y+zはつねにnに合致していなければならないのですが、始めに方針を立てたとき、x, y, zの合計がn以下であれば問題ないと勘違いしていました。

ぴったりN枚の場合のみを考えるので、zの枚数はyの枚数が決まった時点で一つに定まります。
よってループは二重のみで解決します。

#include <stdio.h>
int main(void)
{
    //input
    int N, Y;
    int x, y, z;
    scanf("%d %d", &n, &Y);
    
    for (x = 0; N >= x; x++) {
        for (y = 0; N-x >= y; y++) {
            //for (z = 0; N-x-y >= z; z++) { ...このループは必要ない！
            z = N - x - y;    //代わりにこの行を追加した
                if (Y == 10000*x + 5000*y + 1000*z) {
                    printf("%d %d %d\n", x, y, z);
                    return 0;
                }
            //}
        }
    }
    
    //output
    printf("-1 -1 -1\n");
    return 0;
}

2022/10/8実施
参照先：AtCoder ABC085C-Otoshidama

今後の課題

・条件を勝手に解釈せず、正しく条件の範囲をとらえること