[백준] 14888번 / Java / 연산자 끼워넣기 - 완전탐색, 백트래킹

문제 - (https://www.acmicpc.net/problem/14888)

N개의 수로 이루어진 수열과 N-1개의 연산자로 만들 수 있는 모든 식을 구한다.

구한 수들 중 최대가 되는 값과 최소가 되는 값을 구하고 출력한다.

완전탐색, 백트래킹 문제였다

위 두개 개념만 알면 어렵지 않게 풀 수 있는 문제였기 때문에 간단하게 메모만 해놓고 끝내겠다!

 

문제를 보자마자 나는 재귀를 사용해서 풀어야 겠다고 생각했다.

void cal(int res, int numIdx) 에서 res는 현재까지 계산된 수이고 numIdx는 res와 계산할 수의 인덱스이다.

 

내 풀이를 보면 전역변수로

static int[] op;
static int[] targetOp;

를 볼 수 있다.

op는 문제에서 제시하는 연산자의 갯수를 나타낸다.

op[0]은 "add" 덧셈의 갯수

op[1]은 "sub" 뺄셈의 갯수

op[2]는 "mul" 곱셈의 갯수

op[3]은 "div" 나눗셈의 갯수

targetOp도 연산자를 가르키는 순서는 같지만, 의미는 다르다. 재귀를 파고들면서 현재까지 몇개의 연산자를 사용했는지 표시하는 용도이다.

따라서, 기저사례에서 targetOp배열의 각 인덱스의 수가 op배열과 같아지면 기저로 판단하여 재귀를 종료하게 된다.

 

---

📌주의할 점

• 없음

---

😅실수

• 없음

 

---

코드

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

// 실버1 - 25분
public class InsertOperator {
    static int N;
    static int[] num;
    static int[] op;
    static int[] targetOp;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    static void cal(int res, int numIdx) {
        if (targetOp[0] == op[0] && targetOp[1] == op[1] && targetOp[2] == op[2] && targetOp[3] == op[3]) {
            max = Math.max(max, res);
            min = Math.min(min, res);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (targetOp[i] == op[i]) continue;
            targetOp[i] += 1;
            cal(calculate(res, i, numIdx), numIdx + 1);
            targetOp[i] -= 1;
        }
    }

    static int calculate(int target, int op, int idx) {
        switch (op) {
            case 0: //add
                return target + num[idx];
            case 1: //sub
                return target - num[idx];
            case 2: //mul
                return target * num[idx];
            case 3: //div
                return target / num[idx];
            default:
                return 0;
        }
    }

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

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

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

        cal(num[0], 1);

        System.out.println(max + "\n" + min);
    }
}