[백준] 15658번 : 연산자 끼워넣기 (2) - JAVA [자바]

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

---

dfs 알고리즘 문제이다.
[백준] 14888번 : 연산자 끼워넣기 - JAVA [자바]
문제를 풀어봤으면 매우 쉽게 풀 수 있다.

    public static void dfs(int sum, int depth) {
        if (depth == N) {
            MIN = Math.min(MIN, sum);
            MAX = Math.max(MAX, sum);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (calArr[i] > 0) {
                calArr[i]--;
                if (i == 0) dfs(sum + numArr[depth], depth + 1);
                else if (i == 1) dfs(sum - numArr[depth], depth + 1);
                else if (i == 2) dfs(sum * numArr[depth], depth + 1);
                else dfs(sum / numArr[depth], depth + 1);
                calArr[i]++;
            }
        }
    }

일단 종료 조건은 숫자를 N 개 다 골랐으면 종료한다. 그때의 수식의 결과 값에 따라 최소값 최대값을 업데이트 해준다.

일단 처음 시작은 depth = 1, sum = 수열의 처음 수 이다.
연산자 배열을 0 번째(+)부터 3 번째(/)까지 남은 연산자가 있는지 본다.
연산자를 하나 사용할 것이므로 사용한 연산자의 위치의 배열의 수를 -1 해준다.

각 연산자에 따라 다음 dfs 로 넘겨주는 sum 을 연산자에 맞게 업데이트하여서 넘겨준다. 또한 숫자를 하나 골랐으므로 depth + 1 을 넘겨준다.

위의 연산자를 고른 경우가 끝난 경우 다시 사용한 연산자를 반납해줘야 하므로 즉, 다른 연산자를 쓰는 경우로 바뀌면 연산자의 수를 전으로 돌려야 하므로 마지막에 calArr[i]++ 을 해주어 수를 맞춰준다.

모든 경우를 탐색하여 MAX 와 MIN 을 찾고 출력한다.

여기서 주의할 점이 있는데 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 라고 문제에 나와 있는데, 자바에서는 그냥 나누면 된다.

---

public class bj15658 {

    public static int N, MIN = 1_000_000_001, MAX = -1_000_000_001;
    public static int[] numArr, calArr = new int[4];

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        numArr = new int[N];

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

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

        dfs(numArr[0], 1);

        bw.write(MAX + "\n" + MIN);

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int sum, int depth) {
        if (depth == N) {
            MIN = Math.min(MIN, sum);
            MAX = Math.max(MAX, sum);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (calArr[i] > 0) {
                calArr[i]--;
                if (i == 0) dfs(sum + numArr[depth], depth + 1);
                else if (i == 1) dfs(sum - numArr[depth], depth + 1);
                else if (i == 2) dfs(sum * numArr[depth], depth + 1);
                else dfs(sum / numArr[depth], depth + 1);
                calArr[i]++;
            }
        }

    }
}