[백준] 연산자 끼워넣기 - 14888(Java)

<문제>

• https://www.acmicpc.net/problem/14888
• 수열과 연산자가 주어지면 그걸 조합해 결과가 최대인 것과 최소인 것을 출력하기
• 수열의 순서는 절대 바뀔 수 없고 연산자 우선순위를 무시하여 계산한다.
  • 나눗셈은 정수 나눗셈으로 몫만 취한다. 양수를 음수로 나눌 때는 양수로 바꾸고 몫을 구하고 다시 음수로 바꾼다.

<입력>

• #1: 개수 n
• #2: n개의 수열
• #3: 합이 n-1인 4개의 정수(+ - x ÷ 순)

<출력>

• #1: 결과 최댓값
• #2: 결과 최솟값

<알고리즘>

• 수열 입력값을 받아 배열에 저장
• 결과값을 저장할 배열도 생성(크기 2)
• 재귀탐색을 통해 전체적으로 모두 탐색해서 크기 비교하기(이런 식으로 모두 바꾸는 것이 아니라 하나씩 바꿔서 결과값을 찾을 때는 보통 재귀탐색을 사용한다)
• dfs 재귀함수: 인자(현재 계산된 값, 현재 인덱스-몇번 째 숫자를 사용할 차례인지)

<전체코드>

import java.io.*;
import java.util.*;

public class Main {
    static int n; //개수
    static int[] arr; //숫자배열
    static int[] operator; //연산자개수
    static int max = Integer.MIN_VALUE;
    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());
        arr = new int[n];
        operator = new int[4];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<4; i++) {
            operator[i] = Integer.parseInt(st.nextToken());
        }
        dfs(arr[0],1); //재귀함수 dfs 호출(처음값, 두번쨰 숫자부터)
        System.out.println(max);
        System.out.println(min);
    }
    private static void dfs(int num, int index) {
        if(index == n) { //가진 숫자 모두 사용
            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }
        for(int i=0; i<4; i++) { //4가지 연산중 하나로 계산
            if(operator[i] > 0) { //사용가능 연산자 존재 시
                operator[i]--; //사용함
                switch (i) {
                    case 0: //+
                        dfs(num+arr[index], index+1);
                        break;
                    case 1: //-
                        dfs(num-arr[index], index+1);
                        break;
                    case 2: //x
                        dfs(num*arr[index], index+1);
                        break;
                    case 3: //÷
                        dfs(num/arr[index], index+1);
                        break;
                }
                operator[i]++; //다음 계산을 위해 다시 복구
            }
        }
    }
}