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

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

14888번: 연산자 끼워넣기

백준 14888번 연산자 끼워넣기 문제 링크입니다.

핵심

N개의 수를 받고, N-1개의 연산자를 받는다. 모든 경우의 수를 찾아야 한다. 즉 백트래킹을 통해 모든 경우의 수를 확인하는 재귀 호출 문제이다.

 

정답 코드

import java.util.Scanner;
public class Main {
    public static int max=Integer.MIN_VALUE;
    public static int min=Integer.MAX_VALUE;
    public static int[] number;
    public static int[] operator =new int[4];
    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 idx){
        if(idx==N){
            max= Math.max(max,num);
            min= Math.min(min,num);
            return;
        }
    for(int i=0;i<4;i++){
        if (operator[i]>0){
            operator[i]--;
            switch (i){
                case 0: dfs(num+number[idx],idx+1); break;
                case 1: dfs(num-number[idx],idx+1); break;
                case 2: dfs(num*number[idx],idx+1); break;
                case 3: dfs(num/number[idx],idx+1); break;
            }
            operator [i]++;
        }
    }
    }
}

해설

메인 메서드의 부분은 N개의 수를 배열에 넣고, 연산자의 수를 배열에 넣는 것이다.

중요한 부분은 dfm부분인데, idx가 N이 될대 return 해주는데, 이는 연산자를 모두 사용하였다는 의미이다.

for문을 해석하면, 연산자가 1개라도 남아있다면, 그 연산자를 사용한다는 의미이다.operator의 배열은 차례대로 0,1,2,3 -> +, -, *, /를 의미한다.이후에는 operator를 다시 ++해주어야 한다.

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.