JAVA [Algorithm] - 백준 14888 연산자 끼워 넣기

 

📝문제 설명

---

📢입출력 예시

 

---

✏️문제 풀이

우리는 지금까지 백트래킹 문제를 해결 했을 때 재귀함수로 호출하기 때문에

depth가 마지막까지 도달했을 때 즉, 재귀함수(stack)의 마지막 부분부터 로직을 처리하였다.

 

이번 문제는 연산을 맨 앞부터 수행해야 한다는 점이 지금까지 풀었던 문제와 약간 다른 문제다.

그러므로 생각해야될 것은

 

1. 연산을 수행했으면 그 다음 재귀함수에게 값을 어떻게 전달해 줄 것인가?

2. 연산을 어떻게 앞부터 수행할 것인가?

3. 연산이 완료 되었으면 어떻게 최소, 최대 값을 비교할 것인가?

 

1번을 먼저 해결하기 위해서는 재귀함수에게 연산 후의 값을 매개변수로 전달해주는 식으로 해야한다.

2번을 해결하기 위해서는 1번에서 해결한 문제인 매개변수로 값을 전달해줄 때 switch나 if문으로 연산을 진행 해 준다.

3번을 해결하기 위해서는 연산이 완료된 시점인 depth가 끝까지 도달했을 때 앞에서부터 연산이 완료된 시점이므로 항상 작성했던 depth == N일 때 최소와 최대 값을 비교해준다.

 

package Baekjoon.BackTracking;

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

public class Baek14888 {

    static int[] operation;
    static int[] num;
    static int N, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;

        N = Integer.parseInt(bufferedReader.readLine());
        num = new int[N];
        operation = new int[4];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

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

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for(int i=0; i<4; i++){
            operation[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        backTracking(num[0],0);
        System.out.println(max);
        System.out.println(min);
    }

    private static void backTracking(int currentResult, int depth){

        if(depth == N-1){
            min = Math.min(currentResult, min);
            max = Math.max(currentResult, max);
            return;
        }

        for(int i=0; i<4; i++){
            if(operation[i] > 0){
                operation[i] -= 1;

                switch (i){
                    case 0:
                        backTracking(currentResult + num[depth+1], depth+1);
                        break;
                    case 1:
                        backTracking(currentResult - num[depth+1], depth+1);
                        break;
                    case 2:
                        backTracking(currentResult * num[depth+1], depth+1);
                        break;
                    case 3:
                        backTracking(currentResult / num[depth+1], depth+1);
                        break;
                }

                operation[i] += 1;
            }
        }
    }
}

---

💡새로 알게된 점

이번 백트래킹 문제는 힌트나 다른 블로그의 참고 없이 스스로 풀어서 뿌듯 ~.~

---