14888번: 연산자 끼워넣기

문제

N개의 수로 이루어진 수열과 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자(+, -, ×, ÷)가 주어집니다. 주어진 수의 순서를 바꾸지 않고 연산자를 모두 끼워넣어 만들 수 있는 식의 결과 중, 최댓값과 최솟값을 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 수의 개수 N (2 ≤ N ≤ 11)이 주어집니다. 둘째 줄에는 A1, A2, ..., AN이 주어집니다. 셋째 줄에는 합이 N-1인 4개의 정수(덧셈, 뺄셈, 곱셈, 나눗셈의 개수)가 차례로 주어집니다.
• 출력: 첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력합니다.

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

풀이:  백트래킹

List와 같은 자료구조에 연산자를 모아두었다가 마지막에 한 번에 계산하는 대신, 재귀 함수의 매개변수로 현재까지의 연산 결과(currentSum)를 직접 넘겨가며 계산하는 방법입니다.

• 상태 전달: go 함수의 매개변수로 현재 탐색 중인 수의 인덱스(idx)와 현재까지 누적된 계산 결과(currentSum)를 넘겨줍니다. 초기 호출 시 첫 번째 수(a[0])를 결과값으로 넘깁니다.
• 즉시 계산: 연산자를 선택할 때마다 곧바로 다음 수(a[idx])와 사칙연산을 수행하여 재귀 함수로 넘깁니다.
• 자료구조 조작 생략: 수식이 끝나는 기저 조건(idx == n)에 도달했을 때 별도의 반복문 계산 없이, 전달받은 currentSum으로 즉시 max와 min을 갱신할 수 있습니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    static int[] a;
    static int[] opCnt = new int[4];

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

       // 초기값: 두 번째 수(인덱스 1)부터 탐색, 현재 누적값은 첫 번째 수
       go(1, a[0]);

       bw.write(max + "\n" + min);

       bw.flush();
    }

    static void go(int idx, int currentSum) {
       // 모든 수를 다 연산한 경우 (Base Case)
       if (idx == n) {
          min = Math.min(min, currentSum);
          max = Math.max(max, currentSum);
          return;
       }

       // 백트래킹 탐색 부분 (즉시 연산 적용)
       for (int i = 0; i < 4; i++) {
          if (opCnt[i] == 0) continue;
          
          opCnt[i]--;
          
          if (i == 0) {
             go(idx + 1, currentSum + a[idx]);
          } else if (i == 1) {
             go(idx + 1, currentSum - a[idx]);
          } else if (i == 2) {
             go(idx + 1, currentSum * a[idx]);
          } else {
             go(idx + 1, currentSum / a[idx]);
          }
          
          opCnt[i]++; // 원상 복구
       }
    }
}

알고리즘 분류

브루트포스 알고리즘 (완전탐색), 백트래킹 (Backtracking)