[BJ] 14888 연산자 끼워넣기 Java

백준 14888 연산자 끼워넣기

문제

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

14888번: 연산자 끼워넣기

아이디어

• 사칙연산이 순서대로 주어지기 때문에 사칙연산의 개수를 담는 배열을 만든다
• 이후 사칙연산의 조합을 재귀적으로 호출하여 모든 경우의 수를 확인한다
• 마지막에 사용한 사칙 연산의 개수를 다시 증가시켜줘야한다

코드

import java.util.*;

class BJ14888 {
    static int[] map;
    static int[] operations = new int[4];
    static int n;
    static int MIN = Integer.MAX_VALUE;
    static int MAX = Integer.MIN_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        map = new int[n];

        for (int i=0; i<n; i++) {
            map[i] = sc.nextInt();
        }

        for (int i=0; i<4; i++) {
            operations[i] = sc.nextInt();
        }

        DFS(map[0], 1);
        System.out.println(MAX);
        System.out.println(MIN);
    }

    public static void DFS(int number, int depth) {
        if (depth == n) {
            MAX = Math.max(MAX, number);
            MIN = Math.min(MIN, number);
            return;
        }

        for (int i=0; i<4; i++) {
            if (operations[i] > 0) {
                operations[i]--;
                switch (i) {
                    case 0:
                        DFS(number + map[depth], depth + 1);
                        break;
                    case 1:
                        DFS(number - map[depth], depth + 1);
                        break;
                    case 2:
                        DFS(number * map[depth], depth + 1);
                        break;
                    case 3:
                        DFS(number / map[depth], depth + 1);
                        break;
                }
                operations[i]++;
            }
        }
    }
}