[伯俊]16922号ローマ数字-Java,Java

難易度

銀色.

に答える

<実装エラー>

    static void back(int count, int sum) {
        if (count == n) {
            set.add(sum);
            return;
        }
        back(count + 1, sum + 1);
        back(count + 1, sum + 5);
        back(count + 1, sum + 10);
        back(count + 1, sum + 50);
    }

最初にbacktrackingを以下のように実装し,HashSetを用いて繰返し値を除去した.
しかし、結果はタイムアウトです.
理由を知ると,HashSetにとって,以前に蓄積した値と入力したsum値を最初から比較することで,値を増やす内部アルゴリズムがタイムアウトすることが分かった.
さらに大きな理由は,上記のコードを実行する際の時間的複雑度がO(4^20=199951162776)であり,1億をはるかに超えるためである.
<ソリューション>

HashSetをパージしてアクセスアレイを生成し、重複値を確認します.

バックグラウンドトラッキングを使用すると、枝が実行されます.あるいは低音砲で解決します.

方法1-遡及
バックトラッキングで枝を使うべきで、15650番NとM(2)番を参考にしたほうがいいです.
ここで、VX、VXV、XVVで作成された数字は20で、同じです.
この場合、重複数列であり、重複数列を防止するために、文では初期値がゼロでないことから始まる.

    public static void back(int start, int sum, int count) {
        if (count == n) {
            if (!visit[sum]) {
                visit[sum] = true;
                cnt++;
            }
            return;
        }

        for (int i = start; i < 4; i++) {
            back(i, sum + num[i], count + 1);
        }
    }

方法2-ブルートフォース
1の個数がiの場合、5の個数はj=n-i、10の個数はk=n-i-j、50の個数はl=n-i-j-k

複文を使用して個数を指定して加算します.

アクセスアレイ繰返し判定

cnt世紀

    private static void bruteforce() {
        for (int i = 0; i <= n; i++) { // 1의 개수
            for (int j = 0; j <= n - i; j++) { //5의 개수
                for (int k = 0; k <= n - i - j; k++) { // 10의 개수
                    int l = n - i - j - k; // 50의 개수
                    int sum = i * 1 + j * 5 + k * 10 + l * 50;
                    if (!visit[sum]) {
                        cnt++;
                        visit[sum] = true;
                    }
                }
            }
        }
    }

コード#コード#

package 백트래킹;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ16922 {
    static int n;
    static boolean[] visit;
    static int cnt;
    static int[] num = {1, 5, 10, 50};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        visit = new boolean[50 * 20 + 1];
        bruteforce();
//        back(0, 0, 0);
        System.out.println(cnt);
    }

    private static void bruteforce() {
        for (int i = 0; i <= n; i++) { // 1의 개수
            for (int j = 0; j <= n - i; j++) { //5의 개수
                for (int k = 0; k <= n - i - j; k++) { // 10의 개수
                    int l = n - i - j - k; // 50의 개수
                    int sum = i * 1 + j * 5 + k * 10 + l * 50;
                    if (!visit[sum]) {
                        cnt++;
                        visit[sum] = true;
                    }
                }
            }
        }
    }

    public static void back(int start, int sum, int count) {
        if (count == n) {
            if (!visit[sum]) {
                visit[sum] = true;
                cnt++;
            }
            return;
        }

        for (int i = start; i < 4; i++) {
            back(i, sum + num[i], count + 1);
        }
    }
}