14888번 연산자 끼워넣기 ( JAVA )

접근방법

1. 백트래킹을 통해 연산자를 하나씩 사용하면서 수식을 만든다.

입 / 출력

입력	2 1 1 1 0 0 0	11 100 100 100 100 100 100 100 100 100 100 100 10 0 0 0	3 100 50 25 0 0 0 2
출력	2 2	1100 1100	0 0
입력	5 10 20 30 40 50 1 1 1 1	11 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0	11 1 1 1 1 1 1 1 1 1 1 1 0 10 0 0
출력	2000 -1950	11 11	-9 -9
입력	11 1 1 1 1 1 1 1 1 1 1 1 0 0 10 0	11 1 1 1 1 1 1 1 1 1 1 1 0 0 0 10	4 10 20 30 40 1 2 0 0
출력	1 1	1 1	0 -40

 

코드

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 연산자_끼워넣기 {
    static int n;
    static int maxValue = Integer.MIN_VALUE;
    static int minValue = Integer.MAX_VALUE;
    static int op[];
    static int numbers[];

    public static void main(String[] args) throws IOException {
        // BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        numbers = new int[n];
        String[] intData = br.readLine().split(" ");

        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(intData[i]);
        }

        String[] opData = br.readLine().split(" ");
        op = new int[4];
        for (int i = 0; i < 4; i++) {
            op[i] = Integer.parseInt(opData[i]);
        }
        findOP(0, numbers[0]);
        System.out.println(maxValue);
        System.out.println(minValue);
    }

    static void findOP(int k, int result) {
        if (k == n - 1) {
            maxValue = Math.max(maxValue, result);
            minValue = Math.min(minValue, result);
            return;
        }

        if (op[0] > 0) {
            op[0]--;
            findOP(k + 1, result + numbers[k + 1]);
            op[0]++;
        }

        if (op[1] > 0) {
            op[1]--;
            findOP(k + 1, result - numbers[k + 1]);
            op[1]++;
        }

        if (op[2] > 0) {
            op[2]--;
            findOP(k + 1, result * numbers[k + 1]);
            op[2]++;
        }

        if (op[3] > 0) {
            op[3]--;
            findOP(k + 1, result / numbers[k + 1]);
            op[3]++;
        }

    }

}