백준(BOJ)-14888 연산자 끼워넣기(백 트래킹)[JAVA]

문제

문제 이해 및 코드

백트래킹을 사용하는 알고리즘 문제로, 이해하는데만 많은 시간이 걸렸다. 문제를 접근하는데, 이것저것 해보다가 백준 사이트에 있는 알고리즘 힌트를 보았더니, 완전탐색을 하면서 백트래킹을 하면 된다고 했다. 그림을 그려가면서 접근을 했는데 백트래킹 문제가 처음이라 여전히 감이 안잡혀서, 결국 다른사람이 만든 코드를 보고 이해를 하는식으로 해결했다. 우선 코드부터 보면,

 

코드

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

public class BOJ_14888 {
    public static int MAX = Integer.MIN_VALUE;
    public static int MIN = Integer.MAX_VALUE;
    static int N;
    static int operator[];
    static int number[];
    public static void main(String[] args) throws Exception{
        BufferedReader Br = new BufferedReader(new InputStreamReader(System.in));
        N  = Integer.parseInt(Br.readLine());
        operator = new int[4]; //연산자
        StringTokenizer st;
        number = new int[N]; //피연산자

        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<operator.length;i++)
        {
            operator[i] = Integer.parseInt(st.nextToken());
        }

        dfs(number[0], 1);

        System.out.println(MAX);
        System.out.println(MIN);

    }
    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]++;
            }
        }
    }
}

이를 이해하기위해서 그림을 그려보았다.

 

천천히 접근하다보니깐 왜 이문제가 백트래킹인지 이해가 되었다. 여전히 재귀함수는 어렵다.

 

 

난이도 및 후기

S1 문제로 할만할줄 알았는데, 아직도 어렵다 .. 재귀함수를 이용한 dfs나 백트래킹 문제를 좀더 풀어봐야 겠다.