BOJ 14888 - 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

1. 아이디어

주어진 수열의 순서는 바뀌지 않으므로 그 사이사이 연산자만 끼워넣으면 된다.

 

N-1개의 연산자를 중복 없이 순서있게 나열하여 모든 경우의 수를 탐색하는 완전탐색 문제이다. 

모든 경우를 탐색하면서 최댓값/최솟값이 되는 경우의 연산자 조합을 찾는다.

 

2. 시간복잡도

완전탐색으로 구현하면 중복없이 순서있게 나열하는 순열문제이므로 O(N!)이다.

 

N의 최대값은 11이므로 11! < 2초이므로 가능하다!

 

 

3. 구현

연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

이를 보고 -21억~ 21억의 범위를 가진 int 자료형으로 구현하면 되겠다는 생각을 해야한다.

 

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, max, min;
    static int[] num, operator, order;

    public static void main(String[] args) throws IOException {
        input();

        rec_fuc(1);

        bw.write(max + "\n"+min);
        bw.close();
    }

    static int calculator() {
        // nums, order
        int value = num[1];
        for (int i = 1; i <= N - 1; i++) {

            // 더하기
            if (order[i] == 1) {
                value += num[i + 1];
            }

            // 빼기
            if (order[i] == 2) {
                value -= num[i + 1];
            }

            // 곱하기
            if (order[i] == 3) {
                value *= num[i + 1];
            }

            // 나누기
            if (order[i] == 4) {
                value /= num[i + 1];
            }
        }

        return value;
    }

    private static void rec_fuc(int k) {
        // 한 케이스 선택 완료
        if (k == N) {
            // 결정된 연산자 조합으로 계산 후 갱신
            int value = calculator();
            
            max = Math.max(max, value);
            min = Math.min(min, value);
        } else {
            for (int i = 1; i <= 4; i++) {
                if (operator[i] >= 1) {

                    operator[i]--;
                    order[k] = i;

                    rec_fuc(k + 1);

                    // 다시 초기화
                    operator[i]++;
                    order[k] = 0;
                }


                order[k] = 0;
            }
        }
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        num = new int[N + 1];
        operator = new int[5];

        // order에 연산자들이 순서대로 저장된다.
        order = new int[N + 1];

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

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

        // 최댓값/최솟값 초기화
        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;

    }
}

 

좀 더 빠르게 할 수 있는 방법을 생각해보면

rec_func의 파라미터로 k-1번째 연산자까지 계산한 결과(new_value)까지 넘겨준다면 탐색이 완료되었을 때 value값을 갱신만 해주면 되기 때문에 더 빠르다.

 

넘겨줄 new_value는 기존의 calculator 함수에 피연산자 2개 (value, num[k+1])와 연산자 정보를 넘겨줘서 계산하도록 한다.

 

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, max, min;
    static int[] num, operator, order;

    public static void main(String[] args) throws IOException {
        input();

        // 처음에는 첫 번째 원소가 이제까지 계산된 value값임
        rec_fuc(1, num[1]);

        bw.write(max + "\n"+min);
        bw.close();
    }

    // 이제까지 계산된 value와 다음 계산할 값 operand를 i 연산자로 계산
    static int calculator(int value, int i, int operand) {

        // 더하기
        if (i == 1) {
            return value + operand;
        }

        // 빼기
        if (i == 2) {
            return value - operand;
        }

        // 곱하기
        if (i == 3) {
            return value * operand;
        }

        // 나누기
        if (i == 4) {
            return value / operand;
        }

        return value;
    }

    private static void rec_fuc(int k, int value) {
        // 한 케이스 선택 완료
        if (k == N) {
            max = Math.max(max, value);
            min = Math.min(min, value);
        } else {
            for (int i = 1; i <= 4; i++) {
                if (operator[i] >= 1) {

                    operator[i]--;
                    order[k] = i;

                    int new_value = calculator(value, i, num[k + 1]);

                    rec_fuc(k + 1, new_value);

                    // 다시 초기화
                    operator[i]++;
                    order[k] = 0;
                }


                order[k] = 0;
            }
        }
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        num = new int[N + 1];
        operator = new int[5];

        // order에 연산자들이 순서대로 저장된다.
        order = new int[N + 1];

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

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

        // 최댓값/최솟값 초기화
        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;

    }
}