[백준 14888] 연산자 끼워넣기 [java]

---

두 개의 배열에 각각 숫자와 연산자를 저장한다

 

dfs메소드를 재귀함수로 호출할 건데 매개변수로 하나는 현재 연산된 값과 현재 나온 숫자의 개수를 넘겨준다.

 

예를 들어)

5,6을 숫자로 입력하고

0,0,1,0이 연산자로 입력되면

 

처음에 5와 1(index)을 매개변수로 넘겨주고

index와 입력받은 숫자의 개수가 같지 않으면

for문을 이용해 연산자 배열을 순서대로 확인한다.

 

그래서 다음 매개변수는 5*6인 30과 2가 넘어가게 된다.

 

코드

package baekjoon;

import java.util.Scanner;

public class operator_embed {
    public static int MAX = Integer.MIN_VALUE;
    public static int MIN = Integer.MAX_VALUE;
    public static int[] operator = new int[4];
    public static int[] number;
    public static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        number = new int[n];

        for(int i = 0; i<n;i++){
            number[i] = sc.nextInt();
        }

        for(int i = 0; i<4;i++){
            operator[i] = sc.nextInt();
        }

        dfs(number[0],1);

        System.out.println(MAX);
        System.out.println(MIN);
    }

    public static void dfs(int num, int index){
        if(index == n){ //index의 값이 n과 같아지면 내가 원하는 계산이 끝남
            MAX = Math.max(MAX,num);
            MIN = Math.min(MIN,num);
            return;
        }

        for(int i = 0; i<4;i++){
            //연산자가 하나라도 있으면 if문 안으로 들어온다
            if(operator[i]>0){
                operator[i]--;

                switch (i){
                    case 0:dfs(num + number[index],index+1); break;
                    case 1:dfs(num - number[index],index+1); break;
                    case 2:dfs(num * number[index],index+1); break;
                    case 3:dfs(num / number[index],index+1); break;
                }
                //백트리킹이므로 연산자 개수를 다시 돌려놓아야 한다.
                operator[i]++;
            }
        }
    }
}