[백준] 7490: 0 만들기 - JAVA

in Algorithm on 구현

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

풀이

1부터 N까지의 수 사이에 +, -, 공백을 넣어서 수식을 만들고

그 수식을 계산하여 0이 되는 경우 출력해야 한다.

출력할 때 ASCII 순서에 따라 출력하라는 제한이 있어서 공백, +, - 순서로 dfs탐색을 통해 수식을 만들었다.

N까지 진행하면 수식을 계산하는 메서드를 통해 0이 나오면 값을 출력한다.

메모리: 17200KB

시간: 168ms

언어: Java 11

코드

import java.io.*;

public class Main {

    static int N;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            N = Integer.parseInt(br.readLine());

            dfs(1, "");
            sb.append("\n");
        }

        System.out.println(sb);
    }

    private static void dfs(int idx, String exp) {
        String tmp = exp + String.valueOf(idx);
        if (idx == N) {
            if (cal(tmp) == 0) {
                sb.append(tmp).append("\n");
            }
            return;
        }

        dfs(idx + 1, tmp + " ");
        dfs(idx + 1, tmp + "+");
        dfs(idx + 1, tmp + "-");
    }

    private static int cal(String exp) {
        int sum = 0;
        char sign = '+';
        int prev = 0;
        for (int i = 0; i < exp.length(); i++) {
            if (i % 2 == 0) {
                prev = prev * 10 + (exp.charAt(i) - '0');
            }
            if (i % 2 == 1 || i == exp.length() - 1) {
                if (exp.charAt(i) != ' ') {
                    switch (sign) {
                        case '+':
                            sum += prev;
                            prev = 0;
                            break;
                        case '-':
                            sum -= prev;
                            prev = 0;
                            break;
                    }
                    sign = exp.charAt(i);
                }
            }
        }

        return sum;
    }

}