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

문제

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

14888번: 연산자 끼워넣기

---

풀이

백트래킹 문제입니다. 연산자별로 입력받은 수를 통해, 연산자의 순서를 정하고 계산을 수행하면 됩니다.

 

 순열을 통해 연산자의 순서를 결정할 수 있는데, 일반적인 순열 재귀 시 사용하는 visited 배열을 int[]로 선언하여, 해당 연산자 사용 시에는 해당하는 인덱스 값을 --해주는 것이 문제의 포인트입니다. 

 

아래는 소스 코드입니다.

---

소스코드

import java.util.Scanner;

public class B14888_연산자끼워넣기 {

    static int N;
    static int[] nums;
    static int[] operators = new int[4];
    static int[] selected;
    static int[] visited;
    static int min = Integer.MAX_VALUE;
    static int max = Integer.MIN_VALUE;
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        input();

        selected = new int[N-1];
        visited = new int[4];
        visited = operators.clone();

        perm(0);
        System.out.println(max);
        System.out.println(min);
    }

    static void input(){
        N = sc.nextInt();
        nums = new int[N];
        for(int i = 0;i<N;i++){
            nums[i] = sc.nextInt();
        }
        for(int i = 0;i<4;i++){
            operators[i] = sc.nextInt();
        }
    }

    static void perm(int idx){
        if(idx==N-1){
            calculate(selected);
        }
        else{
            for(int i = 0; i<4;i++){
                if(visited[i]>0) {
                    visited[i]--;
                    selected[idx]=i;
                    perm(idx+1);
                    visited[i]++;
                }
            }
        }
    }

    static void calculate(int[] selected){
        int num = nums[0];

        for(int i = 0;i<N-1;i++){
            if(selected[i]==0) num +=nums[i+1];
            if(selected[i]==1) num -=nums[i+1];
            if(selected[i]==2) num *=nums[i+1];
            if(selected[i]==3) num /=nums[i+1];
        }
        max = Math.max(max,num);
        min = Math.min(min,num);
    }
}