[BOJ] 15658. 연산자 끼워넣기(2)

재귀를 사용해야만 풀수있는 문제이다.

14888.연산자 끼워넣기 와 비슷한 문제이지만 이문제는 연산자의 갯수가 최대 4N개가 주어질 수 있으므로 순열 또는 조합의 방법을 사용할 수 가 없다. 따라서 재귀를 사용해야하는데, 재귀의 조건은 연산자의 종류인 총 4가지가 될 수가 있다. 즉, 숫자와 숫자사이에서 가지고 있는 연산자의 갯수에 따라 4개중 어떤것을 호출하냐를 결정할 수 있다. 기저조건으로는 마지막 index까지 도달했을 경우로 두었다.

보통 재귀는 '했다', '안했다'를 재귀의 요소로 두지만, 이 경우는 '4가지중 어떤것을 했다' 로 두고 풀었다.

package online.base;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_15658_연산자끼워넣기2 {
    
    static int N;
    static int[] numbers;
    
    static int max,min;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        
        numbers=new int[N];
        
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
            numbers[i]=Integer.parseInt(st.nextToken());
        }
        
        int plus,minus,mul,div;
        st=new StringTokenizer(br.readLine());
        plus=Integer.parseInt(st.nextToken());
        minus=Integer.parseInt(st.nextToken());
        mul=Integer.parseInt(st.nextToken());
        div=Integer.parseInt(st.nextToken());
        
        max=Integer.MIN_VALUE;
        min=Integer.MAX_VALUE;
        
        func(numbers[0],1,plus,minus,mul,div);
        
        System.out.println(max);
        System.out.println(min);
    }
    
    static void func(int sum, int index, int plus, int minus,int mul,int div) {
        if(index==N) {
            max=Integer.max(sum, max);
            min=Integer.min(sum, min);
            return;
        }
        
        if(plus>0)
            func(sum+numbers[index],index+1,plus-1,minus,mul,div);
        if(minus>0)
            func(sum-numbers[index],index+1,plus,minus-1,mul,div);
        if(mul>0)
            func(sum*numbers[index],index+1,plus,minus,mul-1,div);
        if(div>0)
            func(sum/numbers[index],index+1,plus,minus,mul,div-1);
    }
    
}