[BOJ_14888] 연산자 끼워넣기

설명

---

연산자 끼워 넣기 연산자의 위치는 그대로고 각각의 기호를 뽑아서 쓴다는 느낌으로 접근했다. 사실 로직 구현 자체는 쉬웠지만 음수 값이 나온다는 것을 간과하여 max의 초기 값을 = 0 으로 잡아서 어디서 틀린지 확인을 많이 했다.

 

코드

---

package Backtracking;

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

public class BOJ_14888 {
    static int arr[];
    static long max;
    static long min;
    static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(in.readLine());

        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        arr = new int[N];

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(tk.nextToken());
        }

        int op[] = new int[4];
        tk = new StringTokenizer(in.readLine()," ");

        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;

        for(int j = 0; j < 4; j++){
            op[j] = Integer.parseInt(tk.nextToken());
        }
        go(0,op,arr[0]);
        System.out.println(max +"\n"+min);
    }

    private static void go(int idx,int[] opertunity,long sum) {
        if(idx == N-1){
            max = Math.max(sum,max);
            min = Math.min(sum,min);
            return;
        }
        for(int i = 0; i < opertunity.length; i++){
            if(opertunity[i] != 0){
                opertunity[i]--;
                if(i == 0) {
                    go(idx + 1, opertunity,sum + arr[idx+1]);
                }
                if(i == 1) {
                    go(idx + 1, opertunity,sum - arr[idx+1]);
                }
                if(i == 2) {
                    go(idx + 1, opertunity,sum * arr[idx+1]);
                }
                if(i == 3) {
                    if(sum < 0) {
                        sum = -(Math.abs(sum) / arr[idx+1]);
                    }else{
                        sum = (sum / arr[idx+1]);
                    }
                    go(idx + 1, opertunity,sum);
                }
                opertunity[i]++;
            }
        }
    }
}

 

14888번: 연산자 끼워넣기