[Baekjoon] 14888번: 연산자 끼워넣기 - Java

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

14888번: 연산자 끼워넣기

문제 설명

수열과 연산자들이 주어지고 그 모든 조합을 찾아 최댓값과 최솟값을 구하는 문제이다. 모든 경우를 탐색해야 하므로 완전탐색 문제이다.

풀이 방법

이 문제는 재귀를 활용하여 해결할 수 있다. 해결 방법이 DFS와 같은 방식이다.

종료 조건은 인덱스와 N의 값이 같을 때인데 N과 같다면 더 이상 할 연산이 없기 때문이다. 그리고 반복이 종료될 때 같이 넘어온 수와 현재 최대, 최솟값을 비교해서 계속 갱신해나가는 방법이다.

연산을 모두 마친 뒤에는 다음 연산을 위해 해당 연산자 개수를 다시 늘려주었다.

public static void solution(int number, int idx) {
    if (idx == N) {
        MAX = Math.max(MAX, number);
        MIN = Math.min(MIN, number);
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (ops[i] > 0) {
            ops[i]--;

            switch (i) {
                case 0:
                    solution(number + numbers[idx], idx + 1);
                    break;
                case 1:
                    solution(number - numbers[idx], idx + 1);
                    break;
                case 2:
                    solution(number * numbers[idx], idx + 1);
                    break;
                case 3:
                    solution(number / numbers[idx], idx + 1);
                    break;
            }

            ops[i]++;
        }
    }
}

전체 코드는 다음과 같다.

package baekjoon.backtracking;

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

public class BOJ14888 {

    private static int MAX = Integer.MIN_VALUE;
    private static int MIN = Integer.MAX_VALUE;
    private static int[] ops;
    private static int[] numbers;
    private static int N;

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

            numbers = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            ops = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            solution(numbers[0], 1);

            System.out.println(MAX);
            System.out.println(MIN);
        }
    }

    public static void solution(int number, int idx) {
        if (idx == N) {
            MAX = Math.max(MAX, number);
            MIN = Math.min(MIN, number);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (ops[i] > 0) {
                ops[i]--;

                switch (i) {
                    case 0:
                        solution(number + numbers[idx], idx + 1);
                        break;
                    case 1:
                        solution(number - numbers[idx], idx + 1);
                        break;
                    case 2:
                        solution(number * numbers[idx], idx + 1);
                        break;
                    case 3:
                        solution(number / numbers[idx], idx + 1);
                        break;
                }

                ops[i]++;
            }
        }
    }
}