[백준] 7490번 : 0 만들기 (JAVA/자바)

[문제 링크]

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

문제 설명

1 ~ N까지 오름차순으로 된 수열의 숫자들 사이에 '+', '-', ' '(공백) 를 적절하게 삽입한다.

이렇게 해서 만들어진 수식을 계산한 결과가 0이 되는 모든 수식을 찾는다.

 

 

 

문제 풀이

알고리즘 분류

• 문자열
• 완전탐색
• 깊이 우선 탐색(DFS)

수식의 결과가 0이 되는 모든 수식을 찾아야 하기 때문에 완전탐색으로 모든 경우의 수를 탐색한다.

1. 재귀함수를 사용해서 숫자들 사이에 +, - " "(공백) 중 하나를 선택해서 만들 수 있는 수식을 문자열 형태로 생성한다. 

dfs(num + 1, str + " " + (num+1));
dfs(num + 1, str + "+" + (num+1));
dfs(num + 1, str + "-" + (num+1));

 

 

하나의 수식이 완성되면 calculate() 함수로 수식의 결과값이 0 이 되는 경우를 찾는다.

문자열로 된 수식을 숫자와 연산자(+, -)로 나눈 후 수식을 계산한다. 

1. 숫자와 숫자 사이가 " "(공백)인 경우, 공백을 제거한다.

    "1 2-3"인 경우, 공백을 제거하면 "12-3"

String express = str.replace(" ", "");

 

2. +, - 의 앞뒤로 공백 한 칸씩을 추가한다.(여기서 추가한 " "(공백)을 기준으로 숫자와 연산자를 나누기 위해)

   "1+2-3" → "1 + 2 - 3"→  {"1", "+", "2", "-", "3"}

String express1 = express.replace("+",  " + ").replace("-", " - ");

 

3. 위의 express1 배열을 공백을 기준으로 나눠서 새로운 배열 strings를 생성한다.

String[] strings = express1.split(" ");

 

4. strings 배열을 처음부터 탐색하면서 +, -를 찾아서 계산한다.

for(int i = 1; i < strings.length; i += 2) {
    if(strings[i].equals("+")) {
        sum += Integer.parseInt(strings[i + 1]);
    } else if (strings[i].equals("-")) {
        sum -= Integer.parseInt(strings[i + 1]);
    }
}

 

 

전체코드

import java.io.*;

public class Main {

    static int n;
    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());

        while(t > 0) {
            n = Integer.parseInt(br.readLine());
            dfs(1, "1");
            sb.append("\n");
            t--;
        }
        System.out.println(sb);
    }

    public static void dfs(int num, String str) {
        if(num == n) {
            if(calculate(str) == 0) {   //수식을 계산에서 값이 0이면 sb에 추가
                sb.append(str + " \n");
            }
            return;
        }

        dfs(num + 1, str + " " + (num+1));
        dfs(num + 1, str + "+" + (num+1));
        dfs(num + 1, str + "-" + (num+1));
    }

    public static int calculate(String str) {
        String express = str.replace(" ", "");  //숫자와 숫자 사이 공백 제거

        /* +. - 앞뒤로 공백 한 칸씩을 추가한 후, " "(공백)을 기준으로 문자열을 쪼갠다.
          1+2-3 -> 1 + 2 - 3 -> {"1", "+", "2", "-", "3"}
        */
        String express1 = express.replace("+",  " + ").replace("-", " - ");
        String[] strings = express1.split(" ");

        int sum = Integer.parseInt(strings[0]);
        for(int i = 1; i < strings.length; i += 2) {
            if(strings[i].equals("+")) {
                sum += Integer.parseInt(strings[i + 1]);
            } else if (strings[i].equals("-")) {
                sum -= Integer.parseInt(strings[i + 1]);
            }
        }
        return sum;
    }
}