[백준] 14888번: 연산자 끼워넣기 - java

문제

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

14888번: 연산자 끼워넣기

 

접근법

전형적인 완전 탐색 + 백트래킹 문제의 유형이었다. 연산자의 우선 순위를 무시하고, 연산자의 개수가 N-1개로 주어진다는 점에서 출제자가 오히려 배려를 해준 것이 아닌가.. 싶었다.

 

코드

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

public class Main {

    static int N;
    static int[] A;
    static int[] operator = new int[4]; // +, -, x, /

    static int min = 1_000_000_001;
    static int max = -1_000_000_001;

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

        N = Integer.parseInt(br.readLine());

        A = new int[N];

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

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

        dfs(1, A[0]);

        sb.append(max).append('\n').append(min);
        System.out.println(sb);
    }

    private static void dfs(int idx, int n) {
        if (idx == N) {
            min = Math.min(min, n);
            max = Math.max(max, n);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (operator[i] > 0) {
                operator[i]--;
                switch (i) {
                    case 0:
                        dfs(idx + 1, n + A[idx]);
                        break;
                    case 1:
                        dfs(idx + 1, n - A[idx]);
                        break;
                    case 2:
                        dfs(idx + 1, n * A[idx]);
                        break;
                    case 3:
                        dfs(idx + 1, n / A[idx]);
                        break;
                }
                operator[i]++;
            }
        }
    }
}

연산자의 시작 위치가 A[0]과 A[1]의 사이이다. 즉, A[0]은 항상 본인의 수 그대로이다. 따라서 dfs 시작할 때 값이 A[0]부터 시작이라는 것에 주의하자.