0만들기 - 7490번

---

풀이 방법

DFS를 이용해서 모두 탐색 후 결과가 0으로 만족되면 list에 저장

list를 정렬 후 출력해줘야함

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static int K, N;
    static ArrayList<String> list = new ArrayList<>();

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

        K = Integer.parseInt(br.readLine());

        for (int i = 0; i < K; i++) {
            list.clear();
            N = Integer.parseInt(br.readLine());
            dfs(1, "");
            Collections.sort(list);
            for(String s: list){
                System.out.println(s);
            }
            System.out.println();
        }
    }

    static void dfs(int num, String s) {
        String str = s + num;
        if (num == N) {
            String temp = str.replaceAll(" @ ", "");
            String[] arr = temp.split(" ");
            int answer = 0;
            boolean check = true;
            for (int i = 0; i < arr.length; i++) {
                if (i % 2 == 1) {
                    if (arr[i].equals("-"))
                        check = false;
                    else
                        check = true;
                    continue;
                }

                if (check) {
                    answer += Integer.parseInt(arr[i]);
                } else {
                    answer -= Integer.parseInt(arr[i]);
                }
            }
            if (answer == 0) {
                str = str.replaceAll(" ", "");
                str = str.replaceAll("@", " ");
                list.add(str);
            }
        } else {
            dfs(num + 1, str + " + ");
            dfs(num + 1, str + " - ");
            dfs(num + 1, str + " @ ");
        }

    }
}