BOJ07490 0 만들기

https://www.acmicpc.net/problem/7490 (opens new window)

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각한다.

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

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

백트래킹

backtracking

private static void backtracking(int depth, int sign, int num, int result, String s) {
    if (depth == n) { // (4)
        result = result + (num * sign);
        if (result == 0) {
            System.out.println(s);
        }
        return;
    }

 
    backtracking(depth + 1, sign, (num * 10) + (depth + 1), result, s + " " + (depth + 1)); // (1)
    backtracking(depth + 1, 1, depth + 1, result + (num * sign), s + "+" + (depth + 1)); // (2)
    backtracking(depth + 1, -1, depth + 1, result + (num * sign), s + "-" + (depth + 1)); // (3)
}

(1) 빈칸인 경우 부호(sign)와 result는 이전과 동일하게 유지된다.
(2), (3) +, - 부호를 만난 경우 result에 연산을 진행한다. (4) depth == n일 때 result가 0이면 조건을 만족하므로 출력한다.

제출 코드

import java.util.Scanner;

public class BOJ7490 {

    private static int n;

    private static void backtracking(int depth, int sign, int num, int result, String s) {
        if (depth == n) {
            result = result + (num * sign);
            if (result == 0) {
                System.out.println(s);
            }
            return;
        }

        backtracking(depth + 1, sign, (num * 10) + (depth + 1), result, s + " " + (depth + 1));
        backtracking(depth + 1, 1, depth + 1, result + (num * sign), s + "+" + (depth + 1));
        backtracking(depth + 1, -1, depth + 1, result + (num * sign), s + "-" + (depth + 1));
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();
        while (t-- > 0) {
            n = scanner.nextInt();

            backtracking(1, 1, 1, 0, "1");

            System.out.println();
        }
    }
}

#BOJ #구현 #브루트포스 알고리즘 #백트래킹