[백준 JAVA] 14888. 연산자 끼워넣기

문제 링크

---

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

접근 방법

---

모든 연산자 조합을 탐색하기 위해 DFS(백트래킹)를 사용합니다.
연산자의 개수만큼 재귀적으로 경우를 나눠서 최댓값과 최솟값을 갱신합니다.

소스 코드

---

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

public class Main {

    static int n, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    static int[] num, cal = new int[4];

    public static void recursive(int depth, int rst) {
        if (n == depth) {
            min = Math.min(min, rst);
            max = Math.max(max, rst);

            return;
        }

        for (int i = 0; i < 4; i++) {
            if(cal[i] != 0) {
                --cal[i];
                if (i == 0) {
                    recursive(depth + 1, rst + num[depth]);
                } else if (i == 1) {
                    recursive(depth + 1, rst - num[depth]);
                } else if (i == 2) {
                    recursive(depth + 1, rst * num[depth]);
                } else {
                    recursive(depth + 1, rst / num[depth]);
                }
                ++cal[i];
            }
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            cal[i] = Integer.parseInt(st.nextToken());
        }

        recursive(1, num[0]);

        System.out.println(max + "\n" + min);
    }
}

코드 설명

---

연산자는 총 4가지(+ - * /)이며, 각 연산자의 개수에 따라 해당 연산자를 선택해 재귀 호출을 진행합니다.
모든 연산 조합을 순회한 후 최댓값과 최솟값을 갱신하여 출력합니다.