[Baekjoon] 7490번 : 0 만들기

1. 문제

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

• 재귀 함수

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

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

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

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

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

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

// 예제 입력 1
2
3
7

// 예제 출력 1
1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

2. 핵심 아이디어

• 자연수 N의 범위(3 <= N <= 9)가 매우 한정적이므로 완전 탐색으로 해결 가능
• 수의 리스트와 연산자 리스트를 분리하여 모든 경우의 수 계산
• 가능한 모든 경우를 고려하여 연산자 리스트를 만드는 것이 관건(재귀 함수 이용)
• 파이썬의 eval() 함수를 이용하여 문자열 형태의 표현식을 계산할 수 있음

3. Python 문제풀이

import sys
import copy

def recursive(arr, n) :
  if len(arr) == n :
    oper.append(copy.deepcopy(arr))
    return
  arr.append(' ')
  recursive(arr, n)
  arr.pop()

  arr.append('+')
  recursive(arr, n)
  arr.pop()

  arr.append('-')
  recursive(arr, n)
  arr.pop()

test_case = int(sys.stdin.readline())

for _ in range(test_case) :
  oper = []
  n = int(sys.stdin.readline())
  recursive([], n-1)

  lst = [i for i in range(1, n+1)]

  for o in oper :
    string = ''
    for i in range(n-1) :
      string += str(lst[i]) + o[i]
    string += str(lst[-1])
    if eval(string.replace(' ', '')) == 0 :
      print(string)
  print()

4. Java 문제풀이

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

class Main {
  static StringBuilder sb = new StringBuilder();

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

    for (int i=0; i<n; i++) {
      number = Integer.parseInt(br.readLine());
      dfs(number, 1, 1, 1, 0, "1");
      sb.append("\n");
    }
    System.out.println(sb.toString());
  }

  static void dfs(int max, int now, int num, int sign, int sum, String str) {
    if (max == now) {
      sum = sum + (num * sign);
      if (sum == 0) {
        sb.append(str + "\n");
      }
      return;
    }
    dfs(max, now+1, num*10+(now+1), sign, sum, str+ " " + String.valueOf(now+1));
    dfs(max, now+1, now+1, 1, sum + (num*sign), str+ "+" + String.valueOf(now+1));
    dfs(max, now+1, now+1, -1, sum + (num*sign), str+ "-" + String.valueOf(now+1));
  }

}