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

문제

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

n개의 숫자와 n-1개의 연산자가 주어졌을 때

숫자의 순서를 유지한 채 연산자의 순서만 바꿔서 계산한 결과의 최댓값, 최솟값을 찾는 문제이다.

풀이

재귀, 백트래킹으로 풀면 되겠다고 생각했는데 뭔가 연산자를 저장하고 있는 배열과 숫자를 저장하고 있는 배열이 달라서 설계하기 헷갈렸다.  

n-1개의 연산자를 모든 순서로 선택하는 방법은 해당 연산자를 선택하거나 선택하지 않거나 둘 중 하나이므로

특정 연산자를 선택하고 재귀로 넘긴 후 다시 선택하지 않는 상태로 백트래킹시키고 다음 연산자를 선택하게 만들면 된다.

4개의 연산자 중 i번째 연산자를 선택했으면 i번째 연산자의 숫자를 1 감소시키고 백트래킹할 때는 다시 1 증가시킨다.

선택한 연산자를 사용하여 현재까지의 결과와 다음 숫자를 연산한 값도 재귀 인자로 같이 넘겨준다.

재귀를 끝내는 조건인 base condition은 n-1개의 연산자를 모두 선택했을 때이다. 현재 탐색 결과가 max보다 크면 max를 갱신시키고 min보다 작으면 min을 갱신시킨다.

참고로 min의 초기값을 0이 아니라 Integer.MIN_VALUE로 해야 한다.

빼기 연산에 의해 min값이 음수가 나올 수 있기 때문이다. 항상 min값을 초기화시킬 때 0으로 하는 것이 습관이 되어서 틀렸다.

코드

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

public class Main {
    static int n;
    static int[] num;
    static int[] calc;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    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());
        }
        st = new StringTokenizer(br.readLine());
        calc = new int[4];
        for(int i=0; i<4; i++){
            calc[i] = Integer.parseInt(st.nextToken());
        }

        dfs(num[0], 1);
        System.out.println(max);
        System.out.println(min);

    }
    static void dfs(int res, int idx){
        if(idx > n-1){
            max = Math.max(max, res);
            min = Math.min(min, res);
            return;
        }

        for(int i=0; i<4; i++){
            if(calc[i] > 0){
                calc[i]--;
                switch(i){
                    case 0:
                        dfs(res+num[idx], idx+1);
                        break;
                    case 1:
                        dfs(res-num[idx], idx+1);
                        break;
                    case 2:
                        dfs(res*num[idx], idx+1);
                        break;
                    case 3:
                        dfs(res/num[idx], idx+1);
                        break;
                }
                calc[i]++;
            }
        }
    }
}