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

[문제]

15658번: 연산자 끼워넣기 (2)

 

📒 문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워 넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수는 N-1보다 많을 수도 있다. 모든 수의 사이에는 연산자를 한 개 끼워 넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워 넣을 수도 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

N개의 수와 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 

📒 문제 해결

DFS 를 이용하여 연산을 반복하고 MAX, MIN을 비교하여 확인한다

 

📒 소스코드

package BOJ.BruteForce;

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

public class boj15658_연산자끼워넣기2 {
    static int N;
    static int[] arr;
    static int[] op;
    static boolean[] visit;
    static int min = Integer.MAX_VALUE;
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        op = new int[4];
        visit = new boolean[N];

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

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < 4; i++) {
            op[i] = Integer.parseInt(st.nextToken());
        }
        dfs(1, arr[0]);
        System.out.println(max);
        System.out.println(min);
    }

    static void dfs(int cnt, int result) {
        if (cnt == N) {
            min = Math.min(min, result);
            max = Math.max(max, result);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (op[i] <= 0)
                continue;

            op[i]--;
            int tmp = result;
            if (i == 0) {
                tmp += arr[cnt];
                dfs(cnt + 1, tmp);
            }

            if (i == 1) {
                tmp -= arr[cnt];
                dfs(cnt + 1, tmp);
            }

            if (i == 2) {
                tmp *= arr[cnt];
                dfs(cnt + 1, tmp);
            }
            if (i == 3) {
                tmp /= arr[cnt];
                dfs(cnt + 1, tmp);
            }
            op[i]++;
        }
    }

}

📒 리뷰

내 제출

 

---

DFS를 이용한 단순 연산을 구현하였습니다.
간단한 Brute-Froce 문제였고 앞서 풀었던 '괄호 추가하기'와 '차이를 최대로'와 비슷한 문제였습니다 😳😳