[백준/JAVA] 14888: 연산자 끼워넣기

[백준/JAVA] 14888: 연산자 끼워넣기

1부터 N까지의 수열이 있을 때 N-1개의 연산자가 주어지면 수와 수 사이에 연산자를 넣는다. 이 결과값의 경우의 수의 최솟값과 최댓값을 구하는 문제이다. 이때 연산자 우선순위를 신경쓰지 않고 왼쪽부터 차례대로 연산하며 수열의 순서는 고정되어 있다. (1, 2, 3...)

기본적으로 브루트 포스로 풀 수밖에 없는 문제이지만 백트래킹을 통해 브루트 포스보다는 실행 시간을 단축시킬 수 있다.

dfs하는 find함수를 순환함수로 구현하여 cnt가 n에 도달할 때까지, 즉 모든 수 사이에 연산자를 넣을 때까지 재귀적으로 호출한 후 cnt == n이 되면 max값과 min값을 업데이트하고 반환한다. for문에서 연산자에 따라 연산의 result값을 find 함수에 매개변수로 주고 호출하면서 함수의 순환이 끝날 때에는 max값과 min값이 구해지게 된다.

처음에는 maxNum값과 minNum값을 각각 100과 0으로 초기화했었는데, 최솟값은 음수가 되는 경우도 있기 때문에 Integer.MIN_VALUE와 같이 초기화해주는 게 안전하다. 또 find 함수의 for문에서 한 경우의 수를 모두 시도했다면 op[i]++를 통해 다음 케이스로 넘어가게 해주어야 한다.

소스코드

---

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

public class Main {
    static int n;
    static int arr[];
    static int op[] = new int[4];
    static int maxNum = Integer.MIN_VALUE;
    static int minNum = Integer.MAX_VALUE;
    // min이 음수가 나오는 경우도 있음

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

        StringTokenizer 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++) {
            op[i] = Integer.parseInt(st.nextToken());
        }
        
        /* N개의 수와 N-1개의 연산자가 주어졌을 때
		 * 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구한다.*/

        find(1, arr[0]);
        System.out.println(maxNum);
        System.out.println(minNum);
    }

    public static void find(int cnt, int result) {
        if (cnt == n) {
            maxNum = Math.max(result, maxNum);
            minNum = Math.min(result, minNum);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (op[i] > 0) {
                op[i]--;
                switch (i) {
                    case 0:
                        find(cnt+1, result+arr[cnt]);
                        break;
                    case 1:
                    	find(cnt+1, result-arr[cnt]);
                        break;
                    case 2:
                    	find(cnt+1, result*arr[cnt]);
                        break;
                    case 3:
                    	find(cnt+1, (int)result/arr[cnt]);
                        break;
                }
                op[i]++;
            }
        }
    }
}