[알고리즘 / 백준] 7490 - 0 만들기

 

문제는 위와 같으며 주어지는 N의 범위가 9이하이기 때문에 모든 경우의 수를 다 계산하는 방향으로 풀이를 해 보았습니다. 모든 경우의 수를 얻기 위해 우선 조합 가능한 연산자 리스트를 재귀함수를 사용하여 생성하였고 이후 연산자 하나하나를 숫자 사이에 넣은 뒤 eval 함수를 사용하여 문자열 그대로 계산되도록 하여 결과를 비교하고 그 값이 0이면 숫자와 연산자 조합을 그대로 출력하도록 하였습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import copy


def recursive(array, length):
    if len(array) == length:
        operator_list.append(copy.deepcopy(array))  # 깊은 복사를 통해 연산자 리스트를 저장
        return

    array.append(' ')
    recursive(array, length)
    array.pop()

    array.append('+')
    recursive(array, length)
    array.pop()

    array.append('-')
    recursive(array, length)
    array.pop()


test_case = int(stdin.readline())

for _ in range(test_case):
    n = int(stdin.readline())
    operator_list = []
    recursive([], n - 1)
    numbers = [i for i in range(1, n + 1)]

    for operators in operator_list:
        string = ""
        # 숫자와 연산자를 차례로 합쳐 하나의 문자열로 만들기
        for j in range(len(operators)):
            string += str(numbers[j]) + operators[j]
        string += str(numbers[-1])

		# 문자열 그대로 계산하기 (" " 는 "" 으로 바꾼 문자열을 가지고 계산)
        if eval(string.replace(" ", "")) == 0:
            print(string)
    print()

 

자바 코드는 다음과 같습니다. 파이썬과 같은 로직으로 구성하였는데 실제 테스트에서 런타임 오류가 발생하네요...

Java 에서 기본적으로 제공되는 eval 함수가 없어서 JavaScript 엔진을 가져와 eval 함수를 사용하였습니다. 이는 Java 1.6 이상에서 사용할 수 있습니다.

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    static List<String[]> operatorList = new ArrayList();

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

        ScriptEngineManager mng = new ScriptEngineManager();
        ScriptEngine engine = mng.getEngineByName("JavaScript");

        int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            int n = Integer.parseInt(br.readLine());
            recursive(new ArrayList(), n - 1);
            int[] nums = new int[n];
            for (int j = 0; j < n; j++) {
                nums[j] = j + 1;
            }

            for (String[] operators : operatorList) {
                StringBuilder sb = new StringBuilder();
                for (int idx = 0; idx < operators.length; idx++) {
                    sb.append(nums[idx]).append(operators[idx]);
                }
                sb.append(nums[nums.length - 1]);
                if ((int) engine.eval(sb.toString().replace(" ", "")) == 0) {
                    System.out.println(sb);
                }
            }
            System.out.println();
        }
    }

    private static void recursive(ArrayList array, int len) {
        if (array.size() == len) {
            String[] operators = new String[array.size()];
            System.arraycopy(array.toArray(), 0, operators, 0, array.size());
            operatorList.add(operators);
            return;
        }

        array.add(" ");
        recursive(array, len);
        array.remove(array.size() - 1);

        array.add("+");
        recursive(array, len);
        array.remove(array.size() - 1);

        array.add("-");
        recursive(array, len);
        array.remove(array.size() - 1);
    }
}

 

런타임 에러가 발생하는 코드지만 우선 올려두겠습니다...ㅠ