문제 출처

단계별로 풀어보기 > 백트래킹 > 연산자 끼워넣기
https://www.acmicpc.net/problem/14888

문제 설명

숫자의 갯수 N, 숫자들, 각각 기호(+,-,*,/)의 갯수가 주어질 때, 주어진 것들을 통해 식을 만들어 최솟값, 최댓값을 return하라
단, 식의 계산은 연산자 우선 순위를 지키지 않고 앞에서부터 계산한다.
숫자는 주어진 순서대로만 계산하고, 기호는 순서를 지키지 않고 계산이 가능하다.

접근 방법

dfs를 이용하여 풀이한다.
각각 숫자를 보관하는 number, 기호를 보관하는 operator를 통해 주어진 숫자와 기호의 갯수를 저장한다.
dfs의 시작으로 num은 number의 처음 원소로 시작하고, 기호의 갯수를 나타내는 idx는 1부터 시작한다.(N == idx가 되면 N-1개의 기호를 사용한 것이기 때문)
dfs 내부에선 N == idx(N-1개의 기호를 사용) 하면 MAX,MIN을 각각 num과 비교하여 최대, 최솟값을 최신화한다.
N == idx가 아닌 경우에는 아직 N-1개의 기호를 사용하지 않았으므로, operator를 순회하여 각각의 기호의 조합을 생성한다.

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class 연산자_끼워넣기 {

    public static int MAX = Integer.MIN_VALUE;
    public static int MIN = Integer.MAX_VALUE;
    public static int[] operator = new int[4];
    public static int[] number;
    public static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i<4; i++){
            operator[i] = Integer.parseInt(st.nextToken());
        }

        dfs(number[0], 1);

        bw.write(MAX + "\n");
        bw.write(String.valueOf(MIN));
        bw.flush();
        bw.close();
        br.close();

    }

    public static void dfs(int num, int idx){
        if (idx == 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: dfs(num + number[idx], idx + 1); break;
                    case 1: dfs(num - number[idx], idx + 1); break;
                    case 2: dfs(num * number[idx], idx + 1); break;
                    case 3: dfs(num / number[idx], idx + 1); break;

                }

                operator[i]++;
            }
        }
    }
}

Review

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

public class 연산자_끼워넣기_review {

    public static int Max = Integer.MIN_VALUE;
    public static int Min = Integer.MAX_VALUE;
    public static int[] number;
    public static int[] sign;

    public static void dfs(int depth, int length, int value){
        if(depth == length){
            Max = Math.max(Max, value);
            Min = Math.min(Min, value);
            return;
        }

        for(int i = 0; i<4; i++) {

            // case로 sign을 받는다.
            if (sign[i] > 0) {
                sign[i]--;
                switch (i) {

                    case 0 : {
                        dfs(depth+1, length, value+number[depth]);
                        break;
                    }
                    case 1 : {
                        dfs(depth+1, length, value-number[depth]);
                        break;
                    }
                    case 2 : {
                        dfs(depth+1, length, value*number[depth]);
                        break;
                    }
                    case 3 : {
                        dfs(depth+1, length, value/number[depth]);
                        break;
                    }
                }
                sign[i]++;
            }
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        number = new int[N];
        sign = new int[4];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            number[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<4; i++){
            sign[i] = Integer.parseInt(st.nextToken());
        }

        dfs(1,N,number[0]);
        bw.write(Max + "\n");
        bw.write(String.valueOf(Min));
        bw.flush();
        bw.close();
        br.close();
    }

}

알게된 점

operator를 사용하지 않고, 각 기호를 직접 배열화 하여 visited만들어서 사용 여부를 체크하려고 했다.
하지만 해당 방법은 꽤나 복잡하여 결국 성공하지 못했다.
operator 자체를 visited처럼 사용하는 방법을 사용하니 식이 정말 깔끔하게 나온다.

출처
https://st-lab.tistory.com/121

Review
dfs를 호출할 때, 연산자는 숫자의 개수의 N-1개이므로, 처음 넘겨주는 숫자는 number의 0번째 수, 그리고 depth는 1로 넘겨줘야한다.
case문을 작성할 때, 조건을 i로 설정하지 않고, sign[i]로 설정해서 틀렸었다.

문제푼 흔적

Review