[백준 풀이_Java] 14888 연산자 끼워넣기 (실버1)

 

백트래킹으로 수를 연산하는 문제였는데

 

백트래킹 연습이 좀 더 필요할 것 같다.

 

핵심은 연산자를 주어진 개수대로 사용하고, 재귀함수를 타면서 주어진 수를 하나씩 사용해 연산하는 것이다.

 

물론, 재귀함수 호출 시 return 과, 결과물 하나를 만든 후 이전 상태로 복구하는 것 까지 고려해야한다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static int N;
    static int[] arithOpr;
    static int[] nums;
    public static int MAX = Integer.MIN_VALUE;
    public static int MIN = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 주어진 수의 개수
        nums = new int[N];
        arithOpr = new int[4]; // 0 0 1 1 연산자

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

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

        recur(nums[0], 0);
        System.out.println(MAX);
        System.out.println(MIN);

    }

    static void recur(int num, int depth){
        // 개수가 N-1이면 리턴
        if(depth == N-1){
            MAX = Math.max(MAX, num);
            MIN = Math.min(MIN, num);
            return; // 리턴 꼭 해줘야함

        }

        for(int i=0; i<4; i++){

            if(arithOpr[i] <= 0) continue;

            // 사용할 연산자가 있다면
            arithOpr[i]--; // 해당 연산자 사용

            switch (i) {
                case 0 : recur(num + nums[depth+1], depth+1); break;
                case 1 : recur(num - nums[depth+1], depth+1); break;
                case 2 : recur(num * nums[depth+1], depth+1); break;
                case 3 : recur(num / nums[depth+1], depth+1); break;
            }

            arithOpr[i]++; // 값 하나 도출 후 해당 연산자 원상복귀
        }
    }
}