[백준/JAVA] 14888번 연산자 끼워넣기 - BruteForce, 백 트랙킹

문제

풀이

DFS를 재귀형식으로 구현하여, 모든 연산자의 경우의 수로 계속 반복하고 마지막 연산이 될 경우 값을 저장하여 최대 최소를 비교하였다.
한번의 재귀가 끝나면 진행되었던 연산자의 개수는 복구시켜야 다른 재귀가 영향을 받지 않는다.

코드

제출 코드

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

class Main {

static int MAX = Integer.MIN_VALUE;
static int MIN = Integer.MAX_VALUE;
static int N;
static int[] arr;
static int[] ops;

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

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

    arr = new int[N];
    ops = new int[4];

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

    st = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < 4; i++) {
        ops[i] = Integer.parseInt(st.nextToken());
    }
    dfs(arr[0], 1);

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


public static void dfs(int post, int idx) {
    if (idx == N) {
        MAX = Math.max(MAX, post);
        MIN = Math.min(MIN, post);
    }
    for (int i = 0; i < 4; i++) {
        if (ops[i] > 0) {
            ops[i]--;
            switch (i) {
                case 0:
                    dfs(post + arr[idx], idx + 1);
                    break;
                case 1:
                    dfs(post - arr[idx], idx + 1);
                    break;
                case 2:
                    dfs(post * arr[idx], idx + 1);
                    break;
                case 3:
                    dfs(post / arr[idx], idx + 1);
                    break;
            }
            ops[i]++;
        }
    }
}

}

공부한 내용

Integer

Integer.MAX_VALUE
Integer.MIN_VALUE

를 사용하면 자료형의 최대 최솟값을 설정해준다.
이를 이용해서 연산의 최대 최소를 비교해서 값을 저장해준다.