[백준] 14888번: 연산자 끼워넣기 (Java)

1. 문제설명

N개의 수로 이루어진 수열에서, 수와 수 사이에 연산자를 하나씩 넣어 수식을 만들 수 있다. 식의 계산은 연산자 우선순위를 무시하고 앞에서부터 진행한다. 나눗셈의 경우 몫만 취하며, 음수를 나눌 때는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼다.

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구한다. (주어진 수의 순서를 바꿀 수 없고, 어떤 식이더라도 -10억보다 크거나 같고, 10억보다 작거나 같은 INT 범위의 결과가 나오는 입력만 주어진다.)

• 시간 제한: 2초
• 메모리 제한: 512MB

 

2. 접근 방식

• 수와 연산자를 배열에 저장한다.
• 모든 경우의 식을 계산해야 한다. ⇒ 완전탐색, 백트래킹
  • 메서드에서 “다음 계산할 수의 인덱스(`numIdx`)”와 “현재까지 계산된 결과(`result`)”를 인자로 받는다.
  • `numIdx` 가 N개이면 `result` 로 최댓값과 최솟값을 갱신한다.
  • for문을 사용하여 연산자를 사용하는 경우의 수를 구한다.
    • 개수가 남아있는 연산자가 있으면 해당하는 연산을 수행하고, 다음 수로 재귀호출한다.
    • 재귀호출 전에 연산자의 개수를 1 감소시키고, 재귀호출 후 다시 복구한다.

 

3. 최종 코드

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

public class Main {
    static int n; // 수의 개수
    static int[] nums; // 수의 배열
    static int[] oper; // 연산자 개수 저장하는 배열
    static int max = Integer.MIN_VALUE; // 최댓값
    static int min = Integer.MAX_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];
        oper = new int[4];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            // n개의 수를 입력받음
            nums[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<4; i++) {
            // 각 연산자 개수를 입력받음
            oper[i] = Integer.parseInt(st.nextToken());
        }

        // 1번째 수부터 계산 시작, 초기 결과값은 0번째 수
        backTrack(1, nums[0]);

        System.out.println(max);
        System.out.println(min);
    }

    // 계산할 인덱스와 현재까지 계산된 결과를 인자로 받음
    static void backTrack(int numIdx, int result) {
        // 모든 수를 계산했을 경우, 최댓값과 최솟값 갱신
        if(numIdx == n) {
            max = Math.max(max, result);
            min = Math.min(min, result);
        }

        for(int j=0; j<4; j++) {
            // 연산자가 남아있으면
            if(oper[j] > 0) {
                int nextResult; // 연산 결과 저장
                if(j==0) { // 덧셈
                    nextResult = result + nums[numIdx];
                } else if(j==1) { // 뺄셈
                    nextResult = result - nums[numIdx];
                } else if(j==2) { // 곱셈
                    nextResult = result * nums[numIdx];
                } else {
                    if(result < 0) { // 음수 나눗셈 처리
                        nextResult = Math.abs(result) / nums[numIdx] * (-1);
                    }
                    else nextResult = result / nums[numIdx];
                }
                oper[j]--; // 연산자 소모
                backTrack(numIdx+1, nextResult); // 다음 수로 재귀호출
                oper[j]++; // 연산자 복구
            }
        }
    }
}