[백준] [14888] 연산자 끼워넣기 (JAVA) (백트래킹)

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

14888번: 연산자 끼워넣기

---

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

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

출력

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

---

※ JAVA (연산자 끼워넣기)

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

public class Main {
    private static int N;
    private static int[] A;
    private static int[] operator; // 연산자
    private static int maxValue = -1000000000; // -10억
    private static int minValue =  1000000000; // 10억

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;


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

        A = new int[N + 1];
        operator = new int[4];

        // 입력받은 수
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        // 연산자 종류 배열
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++) {
            operator[i] = Integer.parseInt(st.nextToken());
        }

        // function start
        // 맨 왼쪽의 값이 A[0]으로 주어지므로 2번째 원소인 인덱스 1부터 시작
        solve(A[0], 1);

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

    public static void solve(int value, int index) {
        if(index == N) {
            minValue = Math.min(value, minValue);
            maxValue = Math.max(value, maxValue);
        }

        for(int i = 0; i < 4; i++) {
            if(operator[i] > 0) { // 사용할 연산자가 존재하면
                operator[i]--; // 사용
                switch (i) { // 0 : +, 1 : -, 2 : *, 3 : /
                    // 덧셈, 뺄셈, 곱셈, 나눗셈 분기
                    case 0: solve(value + A[index], index + 1); break;
                    case 1: solve(value - A[index], index + 1); break;
                    case 2: solve(value * A[index], index + 1); break;
                    case 3: solve(value / A[index], index + 1); break;
                }
                operator[i]++; // 회수
            }
        }
    }
}

---

※ 생각정리 (연산자 끼워넣기)

 

이 문제는 삼성코딩테스트 기출문제로도 유명한 백트래킹 문제이다. 오래전에 풀다가 실패했던 경험이 있었던 문제인 만큼 신중하게 풀었고 추후 다양한 사람들의 코드를 참고하여 간단한 코드를 완성하였다.

 

이해해야할 소스는 다음과 같다.

public static void solve(int value, int index) {
    if(index == N) {
        minValue = Math.min(value, minValue);
        maxValue = Math.max(value, maxValue);
    }

    for(int i = 0; i < 4; i++) {
        if(operator[i] > 0) { // 사용할 연산자가 존재하면
            operator[i]--; // 사용
            switch (i) { // 0 : +, 1 : -, 2 : *, 3 : /
                // 덧셈, 뺄셈, 곱셈, 나눗셈 분기
                case 0: solve(value + A[index], index + 1); break;
                case 1: solve(value - A[index], index + 1); break;
                case 2: solve(value * A[index], index + 1); break;
                case 3: solve(value / A[index], index + 1); break;
            }
            operator[i]++; // 회수
        }
    }
}

 

1. 누적해서 더해 갈 value와 사용할 연산자의 길이이며, 인덱스인 idx를 파라미터에 사용해준다.

 

2. 해당 인덱스가 임의의 개수  N이 된다면 해당 재귀를 종료한다. (항상 백트래킹이던, dfs이건 재귀를 종료할 조건을 추가해주어야한다.)

 

3. 반복문 0 ~ 4까지 반복한다. (이건 연산자 { +, -, *, / }를 담아두었던 배열의 인덱스를 뜻한다)

 

4. 해당 연산자배열에서 잔여연산자가 있다면 사용하며, (조건없이 사용하므로 이는 브루트포스라고 할 수 있다) 연산자가 있으면 그냥 사용하고 다음 재귀로 넘어간다. 조합과도 유사하다

 

5. 각 연산자별로 조건을 넣어 현재 value값에 해당 연산을 누적해 다음 재귀를 보낸다.

 

6. 재귀를 태웠다면 항시 해당 값을 회수해준다. (해당값을 회수해줌으로서 다른 재귀에서 연산자를 사용할 수 있도록 한다)

 

 

- 새벽코딩 -