[Gold V][JAVA]7490번:0 만들기

[Gold V]7490번:0 만들기 - 바로가기

풀이과정

모든 경우의 수를 생성하고 검사하는 브루트 포스(Brute Force) 방식입니다.

1. BF 메소드: 재귀적으로 수식을 생성하고 결과를 계산합니다.

• max: 수열의 최대값 (N)
• now: 현재까지 생성된 수식의 길이
• num: 현재까지 생성된 수식에서 가장 최근에 추가된 숫자
• sign: 현재까지 생성된 수식에서 가장 최근에 추가된 부호(+ 또는 -)
• sum: 현재까지 수식을 계산한 결과
• str: 현재까지 생성된 수식의 문자열 표현

2. 재귀 호출로 수식을 만들어가며, 모든 경우를 탐색합니다.

• '+'나 '-'를 추가하는 경우와 "공백"을 추가하는 경우를 모두 고려합니다.
  

3. sum이 0이 되는 경우 해당 수식을 결과에 추가합니다.

정답

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

 public class Main {  //유형: 브루트포스 / 백트래킹 , 메모리제한: 128 MB, 시간 제한: 1초
     static StringBuilder sb = new StringBuilder();

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

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

     static void BF(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;
         }
         BF(max, now + 1, num * 10 + (now + 1), sign, sum, str + " " + String.valueOf(now + 1));
         BF(max, now + 1, now + 1, 1, sum + (num * sign), str + "+" + String.valueOf(now + 1));
         BF(max, now + 1, now + 1, -1, sum + (num * sign), str + "-" + String.valueOf(now + 1));
     }
 }