백준 7490 0 만들기 (Java)

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

1. 문제

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

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

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

입력

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

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

출력

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

 

2. 풀이

총 9까지의 자연수가 들어갈 수 있으므로 숫자 사이에는 최대 8개의 문자가 들어갈 수 있다. 각 위치에는 세 종류의 문자가 들어갈 수 있으므로 3^8=6561, 전수조사로 해결할 수 있다.

        int t = Integer.parseInt(reader.readLine());

        for (int test = 0; test < t; test++) {

            n = Integer.parseInt(reader.readLine());
            ans = new ArrayList<>();

            opt = new char[n - 1];

 해당하는 숫자를 입력받고, 수식에 들어갈 기호를 char 배열의 opt라는 이름으로 선언해주었다. 숫자가 n개가 들어가면 가능한 기호는 n-1개가 들어간다.

    static void dfs(char inp, int k) {

        if (k == n - 1) {

           //검증 및 리턴
        }

        opt[k] = inp;
        dfs('+', k + 1);
        dfs('-', k + 1);
        dfs(' ', k + 1);



    }

dfs이다. 주어진 3 개의 기호가 들어갈 모든 경우를 탐색한다. 

 

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < n; i++) {
                sb.append(i + 1);
                if (i != n - 1) {
                    sb.append(opt[i]);
                }
            }

            String result = sb.toString();
            String express = result.replaceAll(" ", "");


            //+, -를 포함하여 기호를 기준으로 자르기
            StringTokenizer tokenizer = new StringTokenizer(express, "-|+", true);
            int sum = Integer.parseInt(tokenizer.nextToken());

            while (tokenizer.hasMoreElements()) {
                String s = tokenizer.nextToken();
                if (s.equals("+")) {
                    sum += Integer.parseInt(tokenizer.nextToken());
                }
                if (s.equals("-")) {
                    sum -= Integer.parseInt(tokenizer.nextToken());
                }
            }

            if (sum == 0) {
                ans.add(result);
            }

            return;

기호를 모두 채워넣었을 경우 기호의 끝에 숫자를 채워넣어 수식을 만든다. 수식을 풀기 위해 공백을 붙이고, express라는 문자열을 만들었다. 해당 문자열을 +. -를 기준으로 자르고, 각 기호에 따라 sum을 계산한다. 0을 만들었다면 정답 리스트에 추가한다.

            Collections.sort(ans);

            for (String an : ans) {
                System.out.println(an);
            }

            System.out.println();

ASCII 기준으로 정렬되어야 하므로 정렬 후 이를 출력한다.

 

3. 코드 전문

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

public class Main {

    static int n;
    static char[] opt;
    static List<String> ans;

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(reader.readLine());

        for (int test = 0; test < t; test++) {

            n = Integer.parseInt(reader.readLine());
            ans = new ArrayList<>();

            opt = new char[n - 1];

            dfs('+', 0);
            dfs('-', 0);
            dfs(' ', 0);

            Collections.sort(ans);

            for (String an : ans) {
                System.out.println(an);
            }

            System.out.println();
        }

    }


    static void dfs(char inp, int k) {

        if (k == n - 1) {

            if (inp != '+') {
                return;
            }

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < n; i++) {
                sb.append(i + 1);
                if (i != n - 1) {
                    sb.append(opt[i]);
                }
            }

            String result = sb.toString();
            String express = result.replaceAll(" ", "");


            //+, -를 포함하여 기호를 기준으로 자르기
            StringTokenizer tokenizer = new StringTokenizer(express, "-|+", true);
            int sum = Integer.parseInt(tokenizer.nextToken());

            while (tokenizer.hasMoreElements()) {
                String s = tokenizer.nextToken();
                if (s.equals("+")) {
                    sum += Integer.parseInt(tokenizer.nextToken());
                }
                if (s.equals("-")) {
                    sum -= Integer.parseInt(tokenizer.nextToken());
                }
            }

            if (sum == 0) {
                ans.add(result);
            }

            return;
        }

        opt[k] = inp;
        dfs('+', k + 1);
        dfs('-', k + 1);
        dfs(' ', k + 1);



    }
}