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

1) 생각

N개의 숫자와 N-1개의 연산자가 주어집니다. 

조건은 다음과 같습니다.

1) 연산자의 종류에 상관없이 앞에서부터 계산을 합니다.

2) 숫자는 바뀌지 않고 읽어들인 순서대로 쭉 갑니다.

이 때, 연산자를 이리저리 넣어봤을 때 최소값과 최대값을 출력하시오.

연산결과의 범위가 -10억 ~ 10억 이므로 int형 변수를 선언하여도 풀이가 가능합니다.

연산자를 숫자사이에 이리저리 넣어봤을 때 최소값과 최대값을 출력해야하므로 어떤게 최소값과 최대값이 될지 모릅니다.

주어진 시간초가 2초이고 N의 개수의 최대값이 11 이므로 모든 조건을 따져보아도 시간내 탐색이 가능합니다.

2) 방안

DFS를 통해 + - * / 의 경우를 해당 숫자 카운트를 하면서 하나씩 들어가서 모두 탐색해주었습니다. 탐색을 처음 시작할 경우 맨 앞의 숫자 고정을 위해 Index 0의 숫자를 미리 넣어주었습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main{
    static int[] arr,cul;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++)
            arr[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        cul = new int[4];
        // 더하기 빼기 곱하기 나누기
        for(int i=0;i<4;i++)
            cul[i] = Integer.parseInt(st.nextToken());
        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;
        solve(cul[0],cul[1],cul[2],cul[3],arr[0],1);
        System.out.println(max);
        System.out.println(min);
    }
    
    static int max;
    static int min;
    private static void solve(int plus,int minus,int mul,int div,int result,int idx) {
        if(idx==n) {
            max = Math.max(max, result);
            min = Math.min(min, result);
            return;
        }
        
        // 더하기
        if(plus>0) {
            solve(plus-1,minus,mul,div,result+arr[idx],idx+1);
        }
        // 빼기
        if(minus>0)
            solve(plus,minus-1,mul,div,result-arr[idx],idx+1);
        // 곱하기
        if(mul>0)
            solve(plus,minus,mul-1,div,result*arr[idx],idx+1);
        // 나누기
        if(div>0)
            solve(plus,minus,mul,div-1,result/arr[idx],idx+1);
    }
}