BOJ 14888 - 연산자 끼워넣기

문제

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

 

 

풀이

백트래킹을 이용해 문제를 해결한다

 

백트래킹의 핵심 코드는 다음과 같다

operator[i] -= 1
backtracking(index + 1, sum)
operator[i] += 1
sum = temp

해당 연산자는 사용했으므로 operator[i] -= 1을 해준다

operator[i] == 0 이라면 연산자를 모두 사용했다는 뜻이다

 

이후 연산자를 1개 사용한 채로 backtracking(index + 1, sum)을 실행한다

이는 다음 인덱스와 지금까지 계산한 결과값을 넘겨준다

 

다음으로 operator[i] += 1을 다시 해준다

백트래킹 이전으로 연산자를 다시 선택하지 않은 상태로 만든다

 

마지막으로 sum 값을 다시 원래 값인 temp로 돌린다

이것도 백트래킹 이전으로 sum 값을 원래 값으로 다시 돌려서 다른 연산자로 백트래킹을 새로 시작하기 위함이다

 

 

코드

python

def backtracking(index, sum):
    global minAns
    global maxAns
 
    if index == n - 1:
        if minAns > sum:
            minAns = sum
        if maxAns < sum:
            maxAns = sum
        return
 
    for i in range(4):
        temp = sum
        if operator[i] == 0:
            continue
        if i == 0:
            sum += numArr[index + 1]
        elif i == 1:
            sum -= numArr[index + 1]
        elif i == 2:
            sum *= numArr[index + 1]
        else:
            if sum < 0: 
                sum = abs(sum) // numArr[index + 1] * - 1
            else:
                sum //= numArr[index + 1]
        
        operator[i] -= 1
        backtracking(index + 1, sum)
        operator[i] += 1
        sum = temp
 
 
n = int(input())
numArr = list(map(int, input().split()))
operator = list(map(int, input().split()))
minAns = 1000000001
maxAns = -1000000001
 
backtracking(0, numArr[0])
print(maxAns)
print(minAns)

 

java

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, max, min;
    static int[] nums, operators, order;
    static FastReader scan = new FastReader();
 
    public static void main(String[] args) {
        input();
        rec_func(1);
        System.out.println(max + "\n" + min);
    }
 
    // 피연산자 2개와 연산자가 주어졌을 때 계산해주는 함수
    static int calculator() {
        int value = nums[1];
        for (int i=1; i<=N-1; i++) {
            if (order[i] == 1)
                value = value + nums[i + 1];
            if (order[i] == 2)
                value = value - nums[i + 1];
            if (order[i] == 3)
                value = value * nums[i + 1];
            if (order[i] == 4)
                value = value / nums[i + 1];
        }
        return value;
    }
 
    // order[1...N-1]에 연산자들이 순서대로 저장될 것이다.
    static void rec_func(int k) {
        if (k == N) {
            // 완성된 식에 맞게 계산을 해서 정답에 갱신하는 작업
            int value = calculator();
            max = Math.max(value, max);
            min = Math.min(value, min);
        } else {
            // k 번째 연산자는 무엇을 선택할 것인가?
            for (int cand=1; cand<=4; cand++) {
                if (operators[cand] >= 1) {
                    operators[cand]--;
                    order[k] = cand;
                    rec_func(k + 1);
                    operators[cand]++;
                    order[k] = 0;
                }
            }
        }
    }
 
    static void input() {
        N = scan.nextInt();
        order = new int[N + 1]; // 연산자
        nums = new int[N + 1];
        operators = new int[5];
 
        for (int i=1; i<=N; i++)
            nums[i] = scan.nextInt();
        for (int i=1; i<=4; i++)
            operators[i] = scan.nextInt();
 
        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;
    }
 
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}