[BOJ 14888번] 연산자 끼워넣기 (Java, 완전탐색, 재귀호출)

 

---

문제 링크

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

14888번: 연산자 끼워넣기

---

풀이

- DFS로 연산자에 대한 순열(Permutation)을 구한 후 연산 결과값 구함

- N(2 ≤ N ≤ 11) 이므로 최대 연산자 개수는 10개, 순열 10! = 3,628,800 

- 시간복잡도 O(N! * N ) = O(10! * 11) = 약 3,600만번 이므로 풀이가능

---

제출 코드

 

풀이1. 연산자 순열을 구한 후 연산 처리

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

public class Main {

    static StringBuilder sb = new StringBuilder();

    static int N;

    static int MAX_VALUE = Integer.MIN_VALUE;
    
    static int MIN_VALUE = Integer.MAX_VALUE;

    static int[] operand;

    static int[] operator;

    static int[] selected;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

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

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

        selected = new int[N - 1]; // 연산자 개수 = 피연산자 개수 -1

        br.close();
    }

    static int cal(int v1, int v2, int _op) {
        int result = 0;
        switch(_op) {
            case 0 : {
                result = v1 + v2;
                break;
            }
            case 1 : {
                result = v1 - v2;
                break;
            }
            case 2 : {
                result = v1 * v2;
                break;
            }
            case 3 : {
                result = v1 / v2;
                break;
            }
        }

        return result;
    }

    static void dfs(int cnt) {
        if(cnt == N - 1) {
            int result = operand[0];

            for(int i = 1; i < N; i++) {
                result = cal(result, operand[i], selected[i - 1]);
            }

            MAX_VALUE = Math.max(MAX_VALUE, result);
            MIN_VALUE = Math.min(MIN_VALUE, result);

            return;
        }

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

            operator[i] -= 1;
            selected[cnt] = i;

            dfs(cnt + 1);

            selected[cnt] = 0;
            operator[i] += 1;
        }
    }


    static void pro() {
        dfs(0);

        sb.append(MAX_VALUE).append("\n").append(MIN_VALUE);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}

 

 

풀이2.

https://gksdudrb922.tistory.com/33

백준 14888 - 연산자 끼워 넣기

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int N, ADD, SUB, MUL, DIV;

    static int MAX_VALUE = Integer.MIN_VALUE;
    static int MIN_VALUE = Integer.MAX_VALUE;

    static int[] operand;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

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

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++) {
            int value = Integer.parseInt(st.nextToken());
            if(i == 0) ADD = value;
            else if(i == 1) SUB = value;
            else if(i == 2) MUL = value;
            else DIV = value;
        }

        br.close();
    }

    static void dfs(int idx, int data) {
        if(idx == N) {
            MIN_VALUE = Math.min(MIN_VALUE, data);
            MAX_VALUE = Math.max(MAX_VALUE, data);
        } else {

            // +
            if(ADD > 0) {
                ADD -= 1;
                dfs(idx + 1,  data + operand[idx]);
                ADD += 1;
            }

            // -
            if(SUB > 0) {
                SUB -= 1;
                dfs(idx + 1,  data - operand[idx]);
                SUB += 1;
            }

            // *
            if(MUL > 0) {
                MUL -= 1;
                dfs(idx + 1, data * operand[idx]);
                MUL += 1;
            }

            // /
            if(DIV > 0) {
                DIV -= 1;
                dfs(idx + 1, data / operand[idx]);
                DIV += 1;
            }
        }
    }


    static void pro() {
        dfs(1, operand[0]);

        sb.append(MAX_VALUE).append("\n").append(MIN_VALUE);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}

세번째가 리스트 사용한 경우, 두번째가 배열 사용한 경우, 세번째가 참고하여 dfs 방식 변경

 

 

풀이3. 순열을 구할 때 매번 연산 결과를 넘기는 방식 

- 마지막 if(k == N - 1) 일 때 N만큼 순회하면 연산하지 않아도 되니, 속도 개선됨

- 시간복잡도 : O(10!)

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

public class Main {
    
    static int N, M;
    static int MIN_VALUE, MAX_VALUE;

    static int[] data;
    static int[] operator;
    static StringBuilder sb;

    public static void input() {
        InputProcessor inputProcessor = new InputProcessor();
        N = inputProcessor.nextInt();

        data = new int[N];
        for(int i = 0; i < N; i++) {
            data[i] = inputProcessor.nextInt();
        }

        operator = new int[4];
        for(int i = 0; i < 4; i++) {
            operator[i] = inputProcessor.nextInt();
        }

        sb = new StringBuilder();
        MAX_VALUE = Integer.MIN_VALUE;
        MIN_VALUE = Integer.MAX_VALUE;
    }

    public static void output() throws IOException {
        sb.append(MAX_VALUE).append("\n").append(MIN_VALUE);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

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

        rec(0, data[0]);

        output();
    }

    private static void rec(int k, int value) {
        if(k == N - 1) {
            MAX_VALUE = Math.max(MAX_VALUE, value);
            MIN_VALUE = Math.min(MIN_VALUE, value);
            return;
        }

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

            operator[i] -= 1;
            rec(k + 1, calculate(value, i, data[k + 1]));
            operator[i] += 1;
        }
    }

    private static int calculate(int oprand1, int operator, int oprand2) {
        int result = oprand1;
        if(operator == 0) {
            result += oprand2;
        } else if(operator == 1) {
            result -= oprand2;
        } else if(operator == 2) {
            result *= oprand2;
        } else if(operator == 3) {
            result /= oprand2;
        }

        return result;
    }


    public static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}