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

 

 

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

14888번: 연산자 끼워넣기

풀이

이 문제는 저번과 마찬가지로 백트래킹에 대해 알고있다면 어떠하게 풀지 감이 오는 문제였다. 나는 처음 이문제를 접하였을때 매경우 최적의 경우를 찾아내는 방법이 있는줄 알고 고민하였으나 브루트 포스라는 카테고리를 보고 그냥 전부 돌리기로 생각했다. 여기서 변수는 숫자의 개수를 나타내는 N, 최대값 MAX 최소값 MIN, 숫자들을 담을 arr, 연산자들의 정보를 담을 opr을 사용했다. 자세한 내용은 코드를 보면 이해가 빠를듯 하다.

 

코드

package com.company;


import java.io.*;
import java.util.StringTokenizer;

class Main {

    public static int N;
    public static int MAX = Integer.MIN_VALUE;
    public static int MIN = Integer.MAX_VALUE;
    public static int[] arr;
    public static int[] opr;

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

        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        opr = new int[4];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

        DFS(0, arr[0]);
        System.out.println(MAX + "\n" + MIN);
    }


    public static void DFS(int depth, int val) {
        if (depth + 1 == N) {
            if (MAX < val)
                MAX = val;
            if (MIN > val)
                MIN = val;
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (opr[i] == 0)
                continue;


            opr[i]--;
            switch (i) {
                case 0:
                    DFS(depth + 1, val + arr[depth + 1]);
                    break;
                case 1:
                    DFS(depth + 1, val - arr[depth + 1]);
                    break;
                case 2:
                    DFS(depth + 1, val * arr[depth + 1]);
                    break;
                case 3:
                    DFS(depth + 1, val / arr[depth + 1]);
                    break;
            }
            opr[i]++;
        }
    }
}