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

[문제]

[풀이]

N개의 수의 순서는 고정이어서, 사이사이에 연산자를 넣어 조합해 계산해주면 되는 문제였습니다.

 

우선 number[]에 숫자를 저장하고, operator[]에 각 연산들의 키값의 개수를 저장합니다.

백트래킹을 이용한 makeSet()를 통해 4칙 연산을 수행하며 min과 max값을 뽑아내어 출력합니다.

 

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    // 연산자 끼워넣기
    public static int N;
    public static int[] number;
    public static int[] operator; // 연산자들의 키값을 넣어줌
    public static int max = Integer.MIN_VALUE;
    public static int min = Integer.MAX_VALUE;
    public static ArrayList<String> setArr = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        number = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
            number[i] = Integer.parseInt(st.nextToken());
        }
        operator = new int[4];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<4;i++) {
            operator[i] = Integer.parseInt(st.nextToken());
        }

        makeSet(number[0],1);
        System.out.println(max);
        System.out.println(min);
    }
    public static void makeSet(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++) {
            if(operator[i] > 0) {
                operator[i]--;
                switch (i){
                    case 0:
                        makeSet(num + number[index],index + 1);
                        break;
                    case 1:
                        makeSet(num - number[index],index + 1);
                        break;
                    case 2:
                        makeSet(num * number[index],index + 1);
                        break;
                    case 3:
                        makeSet(num / number[index],index + 1);
                        break;
                }
                operator[i]++;
            }
        }
    }
}