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

📌문제 링크

---

https://www.acmicpc.net/problem/15658

📌문제 설명

---

주어진 숫자들과 연산자들을 이용하여 만들 수 있는 최대값과 최소값을 구하는 문제입니다. 백트래킹을 이용하여 모든 가능한 경우를 탐색합니다. 각 연산자의 개수를 제한하여 조건을 만족하는 결과를 도출합니다.

📌코드

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, add, sub, mul, div, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static int[] arr = new int[11];

    public static void main(String[] args) throws Exception{
        input(); // 입력을 받는 메서드 호출
        solve(); // 문제를 해결하는 메서드 호출
    }

    public static void input() throws Exception {
        N = Integer.parseInt(br.readLine()); // 첫 번째 입력값을 N으로 설정
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken()); // 배열에 입력값 추가
        }
        st = new StringTokenizer(br.readLine());
        add = Integer.parseInt(st.nextToken()); // 더하기 연산자 개수 설정
        sub = Integer.parseInt(st.nextToken()); // 빼기 연산자 개수 설정
        mul = Integer.parseInt(st.nextToken()); // 곱하기 연산자 개수 설정
        div = Integer.parseInt(st.nextToken()); // 나누기 연산자 개수 설정
        br.close(); // BufferedReader 닫기
    }

    public static void backTracking(int idx, int sum, int a, int s, int m, int d) {
        if (idx == N) { // 모든 요소를 다 방문했을 때
            max = Math.max(max, sum); // 최대값 갱신
            min = Math.min(min, sum); // 최소값 갱신
            return;
        }
        if(a < add) backTracking(idx + 1, sum + arr[idx], a + 1, s, m, d); // 더하기 연산
        if(s < sub) backTracking(idx + 1, sum - arr[idx], a, s + 1, m, d); // 빼기 연산
        if(m < mul) backTracking(idx + 1, sum * arr[idx], a, s, m + 1, d); // 곱하기 연산
        if(d < div) backTracking(idx + 1, sum / arr[idx], a, s, m, d + 1); // 나누기 연산
    }

    public static void solve() {
        backTracking(1, arr[0], 0, 0, 0, 0); // 백트래킹 시작
        System.out.println(max); // 최대값 출력
        System.out.println(min); // 최소값 출력
    }
}