[백준] 15658 : 연산자 끼워넣기(2) (JAVA)

문제

BOJ 15658번 : 연산자 끼워넣기(2) - https://www.acmicpc.net/problem/15658

풀이

입력받는 수 n개, 주어지는 연산자의 수는 n-1과 같거나 많음.
+, -, *, / 의 개수가 각각 주어지기 때문에 일단 잘 조합해서 가능한 수식의 경우의 수를 찾아야 한다. => DFS 탐색

첫번째 연산자 자리에 +가 오는 경우, 그리고 첫번째 연산자가 +이면서 두번째 연산자 자리에 +가 오는 경우, 그 다음 세번째 연산자 자리에 -가 오는 경우 ... 이렇게 경우의 수를 구하는 dfs 로직을 짜면 된다.

연산자가 한번 쓰이면, 그 연산자의 남은 개수를 하나 줄여줌으로써 주어진 개수 만큼만을 제한하도록 한다. 예를 들어 주어진 +연산자의 개수가 1개였다면, 첫번째 연산자로 +가 사용되었을 경우 다음 연산자로는 +를 사용할 수 없다.

해당 연산자 위치에 +가 오는 경우, -가 오는 경우, *가 오는 경우, /가 오는 경우를 모두 확인해야 하기 때문에 for문을 사용하여 i=0~3까지(0:+, 1:-, 2:*, 3:/) 돌린다. switch문을 사용하여 해당 연산자에 맞는 연산한 값을 다음 dfs의 sum으로 넘겨준다. idx는 정해진 연산자로 연산될 피연산자의 index를 나타낸다. idx==n일 경우 연산이 완료된 것이기 때문에 결과값(sum)을 min, max와 비교하여 저장한다.

코드

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


public class Main {
    static int n;
    static int[] nums;
    static int[] operator;
    static int result_min = Integer.MAX_VALUE;
    static int result_max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        nums = new int[n];

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

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

        System.out.println(result_max);
        System.out.println(result_min);
    }

    public static void dfs(int idx, int sum){
        if(idx==n){
            result_min = Math.min(result_min, sum);
            result_max = Math.max(result_max, sum);
            return;
        }

        for(int i=0; i<4; i++){
            if(operator[i] == 0) continue;
            operator[i]--;
            switch (i){
                case 0:
                    dfs(idx + 1, sum + nums[idx]);
                    break;
                case 1:
                    dfs(idx + 1, sum - nums[idx]);
                    break;
                case 2:
                    dfs(idx + 1, sum * nums[idx]);
                    break;
                case 3:
                    dfs(idx + 1, sum / nums[idx]);
                    break;
            }
            operator[i]++;
        }


    }

}

\

정리

✔ 알고리즘 분류 - 구현, 브루트포스 알고리즘, 백트래킹
✔ 난이도 - ⚪ Silver 2 

🤦‍♀️ 오늘의 삽질리스트

DFS를 다 돈 후 operator[i]++;을 빼먹어서 값이 이상하게 나왔다. 이런거좀 빼먹지 말자.

참고 사이트

https://whereisusb.tistory.com/231