[Java] 백준 7490 0 만들기

hyunnzl·2024년 12월 23일

algorithm

백준

목록 보기

22/116

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

난이도

골드5

문제

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

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

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

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).
각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

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

내 코드

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

class Main {
	static int num;
	static StringBuilder sb;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		sb = new StringBuilder();

		for (int i = 0; i < tc; i++) {
			num = Integer.parseInt(br.readLine());
			backtracking("1", 2);
			sb.append("\n");
		}
		System.out.println(sb);
	}

	public static void backtracking(String arg, int current) {
		if (current > num) {
			if (cal(arg) == 0) {
				sb.append(arg).append("\n");
			}
			return;
		}

		backtracking(arg + " " + current, current + 1);
		backtracking(arg + "+" + current, current + 1);
		backtracking(arg + "-" + current, current + 1);
	}

	public static int cal(String string) {
		String real = string.replace(" ", "");
		ArrayList<Integer> nums = new ArrayList<>();
		ArrayList<Character> operator = new ArrayList<>();

		String num = "";
		for (char c : real.toCharArray()) {
			if (c == '+' || c == '-') {
				nums.add(Integer.parseInt(num));
				operator.add(c);
				num = "";
			} else {
				num += c;
			}
		}
		nums.add(Integer.parseInt(num));

		int ret = nums.get(0);
		for (int i = 0; i < operator.size(); i++) {
			if (operator.get(i) == '+') {
				ret += nums.get(i + 1);
			} else {
				ret -= nums.get(i + 1);
			}
		}
		return ret;
	}
}