백준 14888번: 연산자 끼워넣기와 상태 복구

연산자를 하나씩 골라 끝까지 계산합니다

백준 14888번 연산자 끼워넣기는 주어진 수 사이에 연산자를 배치해 식을 만들고 그 결과의 최댓값과 최솟값을 구하는 문제입니다. 수의 순서는 유지하며 연산은 앞에서부터 진행합니다.

당시에는 DFS를 재귀로 구현했습니다. 한 경우를 끝까지 따라가는 탐색입니다. post는 지금까지 계산한 값이고 idx는 다음에 사용할 수의 위치입니다. 남아 있는 연산자를 하나 골라 현재 값에 적용하고 다음 수로 넘어갑니다.

모든 수를 사용한 idx == N에서 최댓값과 최솟값을 갱신합니다. 재귀 호출 전에 줄였던 연산자 수는 호출이 끝난 뒤 반드시 복구합니다. 그래야 다음 선택이 앞선 선택의 영향을 받지 않습니다.

제출 코드

Java

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]++;
        }
    }
}

}

최댓값과 최솟값의 시작값

Java

Integer.MAX_VALUE
Integer.MIN_VALUE

Integer.MAX_VALUE는 int의 최댓값, Integer.MIN_VALUE는 최솟값입니다. 첫 계산 결과부터 비교해 저장할 수 있도록 최댓값을 구하는 변수는 가장 작은 값에서 시작합니다. 최솟값을 구하는 변수는 반대로 가장 큰 값에서 시작합니다.