[백준: Java] 7490 - 0 만들기

[문제]

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

 

단순한 백트래킹에 공백이라는 조건을 추가해서 약간의 생각을 하게 만드는 문제였습니다.

---

[초기화]

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

        for (int t = 0; t < tc; t++) {
            n = Integer.parseInt(br.readLine());
            results = new ArrayList<>();
            search("1", 1, 1, 1);
            Collections.sort(results);
            for (String result : results) {
                System.out.println(result);
            }
            System.out.println();
        }
    }

각 테스트케이스마다 입력을 받고 결과를 저장할 리스트를 선언합니다.

 

리스트는 ASCII 순서에 맞게 출력하기 위해 사용됩니다.

 

함수는 항상 1부터 호출합니다.

---

[풀이]

    static void search(String expression, int sum, int prev, int idx) {
        if (idx == n) {
            if (sum == 0) 
            	results.add(expression);
            return;
        }

        int next = idx + 1;

        search(expression + "+" + next, sum + next, next, next);  // 이번 차례에 사용한 값을 prev로 저장
        search(expression + "-" + next, sum - next, -next, next);

        int concat = prev > 0 ? prev * 10 + next : prev * 10 - next;
        search(expression + " " + next, sum - prev + concat, concat, next);
    }

n번까지 번호를 사용하고, 그 시점에 합이 0이라면 결과를 출력할 리스트에 저장합니다.

 

현재 시점에서 사용할 숫자(next)를 생성합니다.

 

이에 맞춰 주어진 연산을 수행하는데, prev를 사용하는 이유는 공백연산 때문입니다.

 

공백은 마지막으로 사용한 수에 10의 배수로 만들어, 현재 시점에 사용할 숫자를 붙이게 됩니다.

 

즉 prev가 2이고 next가 3이라면 20 + 3의 형태로 concat을 생성하고, prev가 -2였다면 next를 붙였을 때도 음수가 되도록 -next를 통해 -23을 만들어 주는 것입니다.

 

마지막으로 지금까지 계산된 sum에 concat 결과를 합치게 되는데, 이전에 사용된 값을 지워줘야 합니다.

 

무슨 말이냐면, sum = 1-2 = -1의 형태를 가지고 있는데 -2를 이용해 -23을 만들어 사용하게 된다면, 이전에 사용한 -2를 없애줘야 한다는 것입니다.

 

그래서 sum - prev를 통해 값을 원상복구시킨 후, 이번에 사용할 concat를 붙이는 것입니다. 그리고 prev는 이번 차례에 사용한 숫자를 저장하므로 prev = concat이 됩니다.

---

[전체 코드]

package 백준.골드;

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

public class BOJ_7490_0만들기 {
    static ArrayList<String> results;
    static int n; 
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());

        for (int t = 0; t < tc; t++) {
            n = Integer.parseInt(br.readLine());
            results = new ArrayList<>();
            search("1", 1, 1, 1);
            Collections.sort(results);
            for (String result : results) {
                System.out.println(result);
            }
            System.out.println();
        }
    }

    static void search(String expression, int sum, int prev, int idx) {
        if (idx == n) {
            if (sum == 0) 
            	results.add(expression);
            return;
        }

        int next = idx + 1;

        search(expression + "+" + next, sum + next, next, next);  // 이번 차례에 사용한 값을 prev로 저장
        search(expression + "-" + next, sum - next, -next, next);

        int concat = prev > 0 ? prev * 10 + next : prev * 10 - next;
        search(expression + " " + next, sum - prev + concat, concat, next);
    }
}

---