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

[백준 14888] 연산자 끼워넣기 : https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

---

문제 조건 정리

 

1. N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다.
2. 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
3. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다.
4. 이때, 주어진 수의 순서를 바꾸면 안 된다.

---

입력

 

1. 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다.
2. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100)
3. 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

---

문제를 풀기 전

 

1. 완전 탐색으로 풀어야함!
2. bfs로 풀기에는 좋지 않아보임!
   
3. 그래서 bfs로 풀어보기로 함!

---

코드

 

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

public class Main {

    private static class State {
        int[] availableOperator;
        int[] selectedOperator;
        int idx;

        // 생성자
        public State(int n, int[] availableOperator) {
            this.availableOperator = Arrays.copyOf(availableOperator, availableOperator.length); // 배열 복사
            this.selectedOperator = new int[n - 1];
            this.idx = 0;
        }

        // 복사 생성자
        public State(State other) {
            this.availableOperator = Arrays.copyOf(other.availableOperator, other.availableOperator.length);
            this.selectedOperator = Arrays.copyOf(other.selectedOperator, other.selectedOperator.length);
            this.idx = other.idx;
        }

    }

    static int n;
    static int[] numbers;
    static int min = Integer.MAX_VALUE;
    static int max = Integer.MIN_VALUE;

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(bufferedReader.readLine());
        numbers = new int[n];
        
        // +, -, *, /
        int[] operators = new int[4];

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        
        stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
        for (int i = 0; i < 4; i++) {
            operators[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        for (int i = 0; i < 4; i++) {
            // operators 배열에 해당 operator가 있다면
            if (operators[i] > 0) {
            
                // 새로운 상태를 만들고
                State initialState = new State(n, operators);
                
                // 상태는 해당 operator를 한 번 사용했음을 표기하고
                initialState.availableOperator[i]--;
                
                // 상태에 선택된 연산자에 등록한다.
                initialState.selectedOperator[initialState.idx++] = i;
                
                // 위 과정을 반복하러 간다.
                bfs(initialState);
            }
        }

        System.out.println(max);
        System.out.println(min);

    }

    private static void bfs(State state) {
        Queue<State> queue = new ArrayDeque<>();
        
        queue.offer(state);

        while (!queue.isEmpty()) {
            State current = queue.poll();
            
            // 해당 상태의 연산자가 놓아진 위치가 마지막에 도달했다면
            if (current.idx == n - 1) {
                calc(current);
                continue;
            }

            for (int i = 0; i < 4; i++) {
                if (current.availableOperator[i] > 0) {
                    // current의 복사본을 생성
                    State next = new State(current); 

                    // 선택한 연산자 사용을 기록
                    next.availableOperator[i]--; 
                    
                    // 연산자 선택을 기록
                    next.selectedOperator[next.idx++] = i;

                    queue.offer(next);
                }
            }
        }
    }

    // 상태에 나열된 연산자와 입력받은 숫자들을 조합해서 계산
    private static void calc(State current) {
        int res = numbers[0];
        for (int i = 0; i < n - 1; i++) {
            switch (current.selectedOperator[i]) {
                case 0:
                    res += numbers[i + 1];
                    break;
                case 1:
                    res -= numbers[i + 1];
                    break;
                case 2:
                    res *= numbers[i + 1];
                    break;
                case 3:
                    res /= numbers[i + 1];
                    break;
            }
        }

        // 최대값과 최소값 갱신
        min = Math.min(min, res);
        max = Math.max(max, res);
    }
}

 

---

문제를 풀고 난 후

 

각 객체에 여러 상태를 저장하는 패턴이 자원을 많이 사용할 것이라고 걱정했으나 생각보다 효율적으로 해결됐음!

하지만 백트래킹 방식이 조금 더 나았을지도 라고 생각함!