[JAVA/백트래킹] 백준 14888 연산자 끼워넣기

1. 문제

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

14888번: 연산자 끼워넣기

 

2. 풀이

백트래킹을 이용해 풀이한다.

• 기호별 사용할 수 있는 남은 갯수를 담은 배열(markCnt)에서 0이 아닌 경우, 즉 기호를 사용할 수 있는 경우 기호를 사용한 계산을 한다.
• 모든 경우를 구하기 위해 재귀함수 실행 후, 기호별 사용할 수 있는 갯수를 다시 늘려준다.(markCnt[i]++)
• 계산식을 끝까지 구한 경우, 이전 값과 비교해 max, min 값을 구한다.

 

3. 코드

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

class Main{
    
    static int n;
    static int[] arr;
    static int[] markCnt; // +, -, *, / 순
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    
    public static void backtracking(int nowVal, int nowIdx) {
        if(nowIdx == n - 1) { // 모든 숫자를 다 사용한 경우
            max = Math.max(max, nowVal);
            min = Math.min(min, nowVal);
            return;
        }
        
        for(int i = 0; i < 4; i++) {
            if(markCnt[i] == 0) continue;
            markCnt[i]--;
            switch(i) {
            case 0: backtracking(nowVal + arr[nowIdx+1], nowIdx+1); break;
            case 1: backtracking(nowVal - arr[nowIdx+1], nowIdx+1); break;
            case 2: backtracking(nowVal * arr[nowIdx+1], nowIdx+1); break;
            case 3: backtracking(nowVal / arr[nowIdx+1], nowIdx+1); break;
            }
            markCnt[i]++;
        }
    }
    
    public static void main (String[] args) throws java.lang.Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        markCnt = new int[4];
        String[] input = br.readLine().split(" ");
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }
        String[] input2 = br.readLine().split(" ");
        for(int i = 0; i < 4; i++) {
            markCnt[i] = Integer.parseInt(input2[i]);
        }
        
       backtracking(arr[0], 0);
        
        System.out.println(max + "\n" + min);
    }
}​