【Java】複数回for文をまわす

解いた問題

AtCoderの「C - Otoshidama」

atcoder.jp

提出した回答

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Y = sc.nextInt();
 
        int x = -1;
        int y = -1;
        int z = -1;
 
        int sheets = 0;
        int sum = 0;
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= (N-i); j++) {
                    sum = (10000 * i) + (5000 * j) + (1000 * (N-i-j));//お札の合計
                    if (Y == sum) {
                        x = i;
                        y = j;
                        z = N-i-j;
                        break;
                    }
 
            }
        }
        System.out.println(x + " " + y + " " + z);
    }
}

自分では回答しきれず、けんちょん先生の記事を参考に回答しました。

qiita.com

自身では見つけられませんでしたが、与えられるお札の枚数が固定されているので、for文は2回で済むのですね。

これまで計算時間のことは考慮できていなくて、とても勉強になりました。0~Nまでのfor文を3回、回すと計算をしなければならないのですね。

先の記事によると

1 秒間で処理できる for 文ループの回数は、=100,000,000 回程度

とのことですので、これからは意識したいと思います。

ダメだった回答

import java.util.Scanner;

//https://atcoder.jp/contests/abc085/tasks/abc085_c
public class Abc085_c {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Y = sc.nextInt();

        int x = -1;
        int y = -1;
        int z = -1;

        int sheets = 0;
        int sum = 0;
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= (N-i); j++) {
                for (int k = 0; k <= (N-i-j); k++) {
                    sheets = i + j + k;//お札の枚数
                    sum = (10000 * k) + (5000 * j) + (1000 * i);//お札の合計
                    if (sheets == N && Y == sum) {
                        x = k;
                        y = j;
                        z = i;
                        break;
                    }
                }
            }
        }
        System.out.println(x + " " + y + " " + z);
    }
}

計算量が多く、TLE（実行時間制限超過）になってしまいました。
問題がしっかり読めておらず「お札の枚数はNで固定で1番内側のfor文の回数を減らせるな」と考えていました。
そもそも「for文の数を減らす」に気づけず悔しいです。

TODO

• 計算量を減らす工夫を勉強し、実践する
  • コードを書いたらより良くならないかレビューする

おわり。。