[JAVA]백준 7490번 0 만들기

📌문제 링크

---

https://www.acmicpc.net/problem/7490

📌문제 설명

---

딱히 까다로운 조건이 없어 재귀로 편하게 풀 수 있는 문제입니다. 공백 문자 연산에 관한 것만 잘 처리하면 됩니다. ASCII 순서에 맞춰 출력을 해야하기 떄문에 공백, +, - 순으로 연산을 진행해야 합니다.

📌코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int T, N;

    public static void main(String[] args) throws Exception {
        T = Integer.parseInt(br.readLine());
        Input();
    }

    public static void Input() throws Exception {
        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine());
            findSolutions();
        }
        br.close();
        bw.flush();
        bw.close();
    }

    public static void backTracking(int current, int number, int sign, int sum, String expression) throws Exception {
        // 현재 숫자가 N과 같으면
        if (N == current) {
            sum = sum + (number * sign);
            // 합이 0이면 결과 출력
            if (sum == 0) {
                bw.write(expression + "\n");
            }
            return;
        }
        // 공백 추가
        backTracking(current + 1, number * 10 + (current + 1), sign, sum, expression + " " + (current + 1));
        // 더하기 추가
        backTracking(current + 1, current + 1, 1, sum + (number * sign), expression + "+" + (current + 1));
        // 빼기 추가
        backTracking(current + 1, current + 1, -1, sum + (number * sign), expression + "-" + (current + 1));
    }

    public static void findSolutions() throws Exception {
        String expression = "1";
        // 백트래킹 시작
        backTracking(1, 1, 1, 0, expression);
        bw.write("\n");
    }
}