[백준] 7490 0 만들기 - Java

 

 

 

문제 출저

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

7490번: 0 만들기

 

 

 

문제 풀이

테스트 케이스 t가 주어지고 t번 만큼 숫자 n이 주어집니다. 

1부터 n까지 차례대로 숫자를 사용하고 숫자 사이에 +. -. " "(공백)을 넣어 수식을 완성합니다. 

공백은 숫자 2개를 붙인다는 의미 입니다. (2 3 => 23) 

수식을 완성하고 계산했을 때, 0이 되는 수식을 구해야 합니다. 

 

dfs를 이용해 전체 수식의 경우의 수를 구했습니다. 

수식은 공백을 붙이기 위해 String으로 구했습니다. String의 replace를 이용해 공백을 없애 숫자를 붙였습니다.

반복문을 이용하여 연산자를 만날 때, 수식의 끝에서 연산을 수행해서 수식의 값을 구했습니다.

수식이 0 이면 출력하게 하여 정답을 구했습니다.

 

 

소스 코드 

package baekjoon.backjoon12.day0110.day09;

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

/*
0 만들기
https://www.acmicpc.net/problem/7490
 */
public class B7490 {

  static int t;
  static int n;
  static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    t = Integer.parseInt(br.readLine());
    while(t-- > 0) {
      n = Integer.parseInt(br.readLine());
      dfs(2, "1");
      sb.append("\n");
    }
    System.out.println(sb);
  }

  public static void dfs(int stage, String formula) {


    if(stage == n+1) {
      if(calculation(formula)) {
        sb.append(formula).append("\n");
      }
      return;
    }

    dfs(stage+1, formula + " " + stage);
    dfs(stage+1, formula + "+" + stage);
    dfs(stage+1, formula + "-" + stage);
  }

  public static boolean calculation(String formula) {
    // 공백 제거
    String nonBlank = formula.replace(" ", "");

    int result = 0;
    char opr = '+';
    String number = "";

    for(int i = 0; i < nonBlank.length(); i++) {
      char c = nonBlank.charAt(i);

      if(Character.isDigit(c)) {
        number += c;
      }

      if(c == '+' || c == '-' || i == nonBlank.length() - 1) {
        int after = Integer.parseInt(number);
        if(opr == '+') result += after;
        else if(opr == '-') result -= after;
        opr = c;
        number = "";
      }
    }
    return result == 0;
  }

}