[伯俊]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);
            }
        }
    }