BOJ 14888 - 연산자 끼워넣기

14888번: 연산자 끼워넣기

 

 

아이디어

 

주어진 순서를 바꾸면 안되니까 연산자만 순서를 잘 조합해서 숫자 사이사이에 끼워넣으면 된다.

 

연산자는 딱 N-1개만큼 주어지고 모두 사용해야 하니까 N-1개의 연산자를 순서있게 나열하는 순열문제이다.

 

연산자를 +, -, *. /  순으로 개수를 받으니까 +를 1, -를 2, *를 3, /를 4로 인덱스를 설정하고

이 인덱스들을 N-1개 만큼 순서있게 나열한 후 인덱스로 연산자를 불러와서 계산하면 된다.

 

 

40분 고민하고 못참고 봐버린 문제.. 살짝 정답이랑 근접하게 고민했던 거에 만족.. ㅠㅠ 실버에서 벽느끼는중...

 

시간복잡도

연산자를 순서있게 나열하는 순열의 시간복잡도는 O(N!)이다.

 

N의 최댓값은 11이니까 11! < 2초라서 가능한 접근법이다. 

 

 

구현

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

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

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

        rec_func(1);


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

    private static void rec_func(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] == 0) continue;

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

                rec_func(k + 1);

                operator[i]++;
                order[k] = 0;
            }
        }
    }

    private static int calculator() {
        int result = nums[1];

        for (int i = 1; i <= N - 1; i++) {

            if (order[i] == 1) {
                result += nums[i + 1];
            }

            if (order[i] == 2) {
                result -= nums[i + 1];
            }

            if (order[i] == 3) {
                result *= nums[i + 1];
            }

            if (order[i] == 4) {
                result /= nums[i + 1];
            }
        }

        return result;

    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        nums = new int[N + 1];
        operator = new int[5];
        order = new int[N];

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

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