BOJ 7490 0 만들기

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

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 … N을 생각하자.

그리고 ‘+’나 ‘-‘, 또는 ‘ ‘(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

---

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

---

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

---

예제 입력 1

2
3
7

예제 출력 1

1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

---

코드

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

public class Main {

    static int max = Integer.MIN_VALUE;
    static StringBuilder[] results;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int[] cases = new int[T];
        
        // 입력받은 N 중 가장 큰 수를 max에 저장
        for (int i = 0; i < T; i++) {
            cases[i] = Integer.parseInt(br.readLine());
            max = Integer.max(max, cases[i]);
        }
        
        // 3 ~ max 각각의 수까지의 수식 결과가 0이 되는 경우를 저장하기 위한 배열 초기화
        results = new StringBuilder[max + 1];
        for (int i = 3; i <= max; i++) {
            results[i] = new StringBuilder();
        }
        
        dfs(1, 1, 1, 0, new StringBuilder("1"));

        // 입력받은 순서대로 각각의 N에 해당하는 결과를 취합해 출력
        StringBuilder answer = new StringBuilder();
        for (int c: cases) {
            answer.append(results[c]).append('\n');
        }

        System.out.println(answer);
    }

    static void dfs(int idx, int prev, int op, int sum, StringBuilder express) {
        if(prev * op + sum == 0) {
            results[idx].append(express).append('\n');
        }

        if(idx == max) {
            return;
        }

        int newIdx = idx + 1;

        // 수식이 ASCII 순으로 정렬된 상태로 저장하기 위해, 연산 순서를 ' ' -> '+' -> '-' 순으로 설정함
        dfs(newIdx, prev * 10 + newIdx, op, sum, new StringBuilder(express).append(' ').append(newIdx));
        dfs(newIdx, newIdx, 1, prev * op + sum, new StringBuilder(express).append('+').append(newIdx));
        dfs(newIdx, newIdx, -1, prev * op + sum, new StringBuilder(express).append('-').append(newIdx));
    }
}