19.연산자 끼워넣기

📍 문제 설명

 

💡 접근

숫자 사용횟수와 연산 결과값을 이용하는 재귀함수를 만들어서 계산해주기

1,2,3,4,5,6 / 덧셈 2 뺄셈 1 곱셈 1 나눗셈 1

d(1,1)일 때 / 1

add = 1 연산결과 1+2 = 3 d(2,3) 

add = 0 연산결과 1+2+3 = 6 d(3,6)

sub = 0 연산결과 1+2+3-4 = 2 d(4,2)

mul = 0 연산결과 1+2+3-4*5 = 10 d(5,10)

div = 0 연산결과 1+2+3-4*5/6 = 1 d(6,1)

 

이런식으로 모든 연산식에 대해서 최댓값/최솟값을 n번 사용할 때 마다 기록해준다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n;
    static int add, sub, mul, div;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    static int[] arr;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt(); //숫자의 갯수

        arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        //덧셈,뺄셈,나눗셈,곱셈의 갯수
        add = kb.nextInt();
        sub = kb.nextInt();
        mul = kb.nextInt();
        div = kb.nextInt();
        //상하좌우 탐색했던 것 처럼 4개의 연산자에 대해서 탐색한다.

        //숫자 갯수, 연산 결과
        dfs(1, arr[0]);
        System.out.println(max);
        System.out.println(min);

    }

    private static void dfs(int i, int now) {
        //숫자를 n번 사용했을 경우 최솟값 최댓값 구해보기
        if(i == n) {
            max = Math.max(max, now);
            min = Math.min(min, now);
        }
        //각 연산자에 대해서 재귀호출
        else {
            if(add > 0) {
                add--;
                dfs(i + 1, now + arr[i]);
                add++;
            }
            if(sub > 0) {
                sub--;
                dfs(i + 1, now - arr[i]);
                sub++;
            }
            if(mul > 0) {
                mul--;
                dfs(i + 1, now * arr[i]);
                mul++;
            }
            if(div > 0) {
                div--;
                dfs(i + 1, now / arr[i]);
                div++;
            }
        }
    }
}