문제

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

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

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

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

---

입력

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

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

---

출력

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

---

풀이

접근방법

시간제한 1초, 메모리128MB, (1 ≤ N ≤ 9)이다.

N이 충분히 작으므로 DFS로 확인해본다.

수식을 먼저 만든뒤에 계산을 하는 방식을 사용했다.
가장 단순해보여 위와 같은 방식으로 접근했지만, 문자열을 파싱하는 과정에서 손해를 보는것 같다.
계산과정에서 바로바로 계산을 하는게 조금 더 깔끔할듯하다.

주의할점! ASCII 순서에 따라 결과를 출력해야한다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	static int N;
	static StringBuilder sb;
	static char[] operator = {' ', '+', '-'};
	static char[] choice;

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

		int T = stoi(in.readLine());
		for (int tc = 0; tc < T; ++tc) {
			N = stoi(in.readLine());
			choice = new char[N - 1]; // 연산자는 N-1개 존재한다.
			int depth = 0;
			for (int i = 0; i < 3; ++i) {
				choice[depth] = operator[i];
				simulation(depth + 1);
			}
			sb.append("\n");
		}
		System.out.println(sb);

	}

	private static void simulation(int depth) {
		if (depth >= N - 1) {
			List<Integer> list = new ArrayList<>();
			for (int i = 1; i <= N; ++i)
				list.add(i);

			StringBuilder expBuilder = new StringBuilder();
			for (int i = 0; i < N - 1; ++i) {
				expBuilder.append(list.get(i)).append(choice[i]);
			}
			expBuilder.append(N);

			String exp = expBuilder.toString(); // 수식을 완성
			String valueExp = exp.replaceAll(" ", ""); // 공백을 제거한다.
			String[] nums = valueExp.split("[\\-\\+]"); // 숫자만 추린다.

			int result = stoi(nums[0]);
			int index = 1;
			for (int i = 0; i < N - 1; ++i) {
				if (choice[i] == '+') {
					result += stoi(nums[index]);
					index++;
				}
				if (choice[i] == '-') {
					result -= stoi(nums[index]);
					index++;
				}
			}

			if (result == 0)
				sb.append(exp).append("\n");

			return;
		}
		for (int i = 0; i < 3; ++i) {
			choice[depth] = operator[i];
			simulation(depth + 1);
		}
	}

	private static boolean isNumber(char c) {
		if ('1' <= c && c <= '9')
			return true;
		return false;
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}