[백준] 연산자 끼워넣기

문제

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

 

 

 

풀이

1. 입력 처리
   • n개의 숫자를 입력받고, 리스트 arr에 저장.
   • 덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수를 입력받음.
2. DFS(백트래킹) 활용
   • dfs(i, now): 현재 i번째 숫자를 처리 중이고, now는 현재까지 계산된 값.
   • 모든 숫자를 처리하면 minValue, maxValue 갱신.
   • 남아있는 연산자를 하나씩 사용하면서 백트래킹 수행.
3. 연산 적용 방식
   • 덧셈, 뺄셈, 곱셈, 나눗셈 연산자가 남아있다면 사용 후 dfs 재귀 호출.
   • 연산 후에는 원상 복구하여 다른 경우의 수를 탐색할 수 있도록 함.
4. 결과 출력
   • maxValue: 가능한 수식 중 가장 큰 값.
   • minValue: 가능한 수식 중 가장 작은 값.

 

 

import java.util.*;

public class Main {

    public static int n;
    // 연산을 수행할 수 리스트
    public static ArrayList<Integer> arr = new ArrayList<>();
    // 덧셈, 뺄셈, 곱셈, 나눗셈 연산자 개수
    public static int add, sub, mul, div;

    public static int minValue = (int) 1e9;
    public static int maxValue = (int) -1e9;

    // i : 현재 진행 중인 숫자의 인덱스, now : 현재까지 계산된 값
    public static void dfs(int i, int now) {
        // 모든 숫자들을 다 사용한 경우 (연산이 끝난 경우)
        if (i == n) {
            // 최솟값, 최댓값 갱신
            minValue = Math.min(minValue, now);
            maxValue = Math.max(maxValue, now);
        } else {
            // 각 연산자에 대하여 재귀적 수행
            if (add > 0) {
                add--;  // 연산자 사용 감소
                dfs(i + 1, now + arr.get(i));  // 다음 숫자로 진행
                add++;  // 백트래킹 (원상 복구)
            }
            if (sub > 0) {
                sub--;
                dfs(i + 1, now - arr.get(i));
                sub++;
            }
            if (mul > 0) {
                mul--;
                dfs(i + 1, now * arr.get(i));
                mul++;
            }
            if (div > 0) {
                div--;
                dfs(i + 1, now / arr.get(i));
                div++;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            arr.add(x);
        }

        add = sc.nextInt();
        sub = sc.nextInt();
        mul = sc.nextInt();
        div = sc.nextInt();

        dfs(1, arr.get(0));

        System.out.println(maxValue);
        System.out.println(minValue);
    }
}