BOJ 14888 - 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

---

 

dfs를 활용하면 비교적 쉽게 해결할 수 있다.

연산자의 종류는 4가지이기 때문에 길이 4를 가지는 배열을 선언하고 각가 연산자의 개수를 담는다.

그 후, 배열 길이만큼의 반복문에서 재귀호출을 해주며 인덱스를 줄여주면 해결이 가능하다.

 

 

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

public class Main {
    static int NUMBER;
    static int[] ARR;
    static int[] OPERATOR = new int[4];
    static int MIN = Integer.MAX_VALUE;
    static int MAX = Integer.MIN_VALUE;

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

        for (int i = 0; i < NUMBER; i++) {
            ARR[i] = Integer.parseInt(st.nextToken());
        }

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

        dfs(ARR[0], 1);

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

    public static void dfs(int result, int depth) {
        if (depth == NUMBER) {
            MIN = Math.min(MIN, result);
            MAX = Math.max(MAX, result);

            return;
        }

        // 연산을 하나씩 해본다.
        for (int i = 0; i < 4; i++) {
            if (OPERATOR[i] > 0) {
                OPERATOR[i]--;
                switch (i) {
                    case 0 :
                        dfs(result + ARR[depth], depth + 1);
                        break;
                    case 1 :
                        dfs(result - ARR[depth], depth + 1);
                        break;
                    case 2 :
                        dfs(result * ARR[depth], depth + 1);
                        break;
                    case 3 :
                        dfs(result / ARR[depth], depth + 1);
                        break;
                }
                OPERATOR[i]++;
            }
        }
    }

}