백준 14888번 - '연산자 끼워넣기'

1. 문제

백준 14888번(연산자 끼워넣기)

N개의 수로 이루어진 수열이 주어지고, N - 1개의 연산자가 주어집니다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(x), 나눗셈(÷) 으로만 이루어져 있습니다. 이 연산자들은 연산자 우선순위를 무시하고, 앞에서 부터 연산을 합니다. 이때, 구할수 있는 최대값과 최소값을 구하시오. 나눗셈의 경우에는 몫만 취하고 나머지 값은 버립니다. 그리고 음수를 양수로 나눌때는 음수를 양수로 바꾼 뒤 몫을 취하고, 몫을 음수로 바꾸어 계산 합니다.

 

 

2. 접근(추상)

1. 주어진 연산자들(n-1개) 중에 n-1개를 뽑아야 합니다.

2. 하지만, 이 연산자들의 순서에 따라서, 값이 달라집니다.

3. 따라서, 순열을 사용합니다.

4. 연산자들 중 중복으로 사용 가능한 연산자도 주어집니다.

5. 따라서, 중복 순열을 사용하여, 모든 경우의수를 구합니다.

6. 중복 순열은 DFS로 구할수 있습니다.

 

 

3. 접근(구현)

1. 덧샘, 뺄샘, 곱샘, 나눗샘의 개수와 수열을 초기화 합니다.

2. dfs 함수를 정의 합니다.

3. 파라미터로 연산자의 카운터의 개수, 현재 진행 중인 값으로 정의 합니다.

4. 재귀 함수의 탈출 조건으로 연산자의 카운터의 개수가 입력 받은 n-1개와 같다면 탈출 합니다.

5. 그렇지 않다면, 덧샘, 뺄샘, 곱샘, 나눗샘 연산자를 하나씩 뽑으면서 연산(1감소)을 진행 합니다. 연산자의 카운터 개수도 1씩 증가 시켜 줍니다.

6. 현재 연산자를 뽑지 않은 경우를 위해 덧샘, 뺄샘, 곱샘, 나눗샘 연산자를 1증가 시켜 줍니다.

7. 재귀 함수 진행 과정에서 최소값과 최대값을 갱신 합니다.

 

 

4. java 소스

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

public class BOJ14888 {
    // https://www.acmicpc.net/problem/14888
    // 연산자 끼워 넣기
    public static void main(String[] args) throws IOException {
        // n의 최대값 = 11, n-1 = 10
        // n-1Pn-1 순열로 모든 경우의 수를 따져볼수 있음
        // 이때 최대값을 통해 시간복잡도를 미리 따져봐야 함
        // 하지만, 같은 연산자가 여러개 존재 합니다.
        // 따라서, 중복이 허용되는 순서있는 조합
        // 중복 순열을 사용하여 푼다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n;
        int[] values;
        int plus, minus, multiple, divide;

        // 원소 갯수 초기화
        n = Integer.parseInt(st.nextToken());

        // 전체 수 초기화
        values = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            values[i] = Integer.parseInt(st.nextToken());
        }

        try {
            // 연산자 갯수 초기화
            st = new StringTokenizer(br.readLine());
            plus = Integer.parseInt(st.nextToken());
            minus = Integer.parseInt(st.nextToken());
            multiple = Integer.parseInt(st.nextToken());
            divide = Integer.parseInt(st.nextToken());
        } finally {
            br.close();
        }

        MaxAndMinFinder maxAndMinFinder = new BOJ14888().new MaxAndMinFinder(values, plus, minus, multiple, divide);

        final int maxValue = maxAndMinFinder.getMaxValue();
        final int minValue = maxAndMinFinder.getMinValue();

        System.out.println(maxValue);
        System.out.println(minValue);
    }

    class MaxAndMinFinder {
        private int plus, minus, multiple, divide;
        private int maxValue, minValue;
        private int[] values;
        private int operatorNum;

        public MaxAndMinFinder(int[] values, int plus, int minus, int multiple, int divide) {
            this.operatorNum = values.length - 1;
            this.values = values;
            this.minValue = (int) 1e9;
            this.maxValue = (int) -1e9;
            this.plus = plus;
            this.minus = minus;
            this.multiple = multiple;
            this.divide = divide;

            dfs(0, values[0]);
        }

        public void dfs(int cnt, int value) {
            // 모든 연산자를 닫 뽑은 경우
            if (cnt == operatorNum) {
                minValue = Math.min(minValue, value);
                maxValue = Math.max(maxValue, value);
            } else {
                // 덧셈 연산자를 뽑는 경우
                if (plus > 0) {
                    plus--;
                    dfs(cnt + 1, value + values[cnt + 1]);
                    plus++;
                }

                // 뺄샘 연산자를 뽑는 경우
                if (minus > 0) {
                    minus--;
                    dfs(cnt + 1, value - values[cnt + 1]);
                    minus++;
                }

                // 곱샘 연산자를 뽑는 경우
                if (multiple > 0) {
                    multiple--;
                    dfs(cnt + 1, value * values[cnt + 1]);
                    multiple++;
                }

                // 나눗샘 연산자를 뽑는 경우
                if (divide > 0) {
                    divide--;
                    dfs(cnt + 1, value / values[cnt + 1]);
                    divide++;
                }
            }
        }

        public int getMaxValue() {
            return this.maxValue;
        }

        public int getMinValue() {
            return this.minValue;
        }
    }
}

 

 

5. 순열에 대해서

순열 알고리즘

 

 

6. DFS, BFS

백준 18352번 - '특정 거리의 도시 찾기'