読者です 読者をやめる 読者になる 読者になる

AOJ 1237: Shredding Company

競技プログラミング AOJ

問題

Shredding Company | Aizu Online Judge

解法

DFS

コード

import java.util.Scanner;

public class Main {
    private static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            N = sc.nextInt();
            String M = sc.next();
            if (N == 0) {
                sc.close();
                break;
            }

            String log = DFS(M, 0, "");
            int ans = Integer.parseInt(log.split(" ")[0]);
            if (ans == -1) {
                System.out.println("error");
                continue;
            }

            String[] pieces = log.split(" ")[1].split(",");
            int testsum = 0;
            for (int i = 0; i < pieces.length; i++) {
                if (!pieces[i].equals("")) {
                    testsum += Integer.parseInt(pieces[i]);
                }
            }
            if (testsum > ans) {
                System.out.println("rejected");
                continue;
            }

            System.out.print(ans);
            for (int i = 0; i < pieces.length; i++) {
                if (!pieces[i].equals("")) {
                    System.out.print(" " + pieces[i]);
                }
            }
            System.out.println();

        }

    }

    static String DFS(String rest, int sum, String log) {
        // restは残った文字列、sumは使った部分文字列の和、
        // logは使った部分文字列の区切り方
        int ans = -1;// 見つかった最適な答え
        String logger = "";// 区切り方を記録しておく

        for (int i = 1; i <= rest.length(); i++) {
            // 残った文字列のi文字目までを切り出す
            int p = Integer.parseInt(rest.substring(0, i));

            if (i == rest.length()) {
                if (sum + p <= N) {
                    if (sum + p > ans) {
                        ans = sum + p;
                        logger = log + "," + rest.substring(0, i);
                    } else if (sum + p == ans) {
                        logger = logger + "," + log + ","
                                + rest.substring(0, i);
                    }
                }
            } else if (sum + p <= N) {
                String t = DFS(rest.substring(i), sum + p,
                        log + "," + rest.substring(0, i));
                int tmp = Integer.parseInt(t.split(" ")[0]);
                if (tmp <= N && tmp > 0) {
                    if (ans < tmp) {
                        ans = tmp;
                        logger = t.split(" ")[1];
                    } else if (ans == tmp) {
                        logger = logger + "," + t.split(" ")[1];
                    }
                }
            }

        }

        return String.valueOf(ans) + " " + logger;

    }
}