[Algorithm] 연산자 끼워 넣기

풀이

연산자를 숫자 사이에 끼워넣는데, 순서 상관 없이 끼워넣어 모든 경우를 구하는 것과 같다.

dfs로 구현했다.

 

dfs를 구현할 때, 파라미터로 index와 지금까지 연산한 결과 now를 전달한다.

dfs의 재귀호출의 깊이가 깊어질수록 number의 index는 n에 가까워지고

그때까지 연산의 결과를 유지해야 했다.

 

index가 n에 도달하면 최대 최소 비교하도록 했다.

 

그리고 연산자의 경우 d 라는 배열로 관리했는데, 오히려 헷갈리기 때문에

깃헙의 풀이와 같이 각각의 변수로 관리하는 것이 코드를 보는데 더 편하다.

 

소스코드

import java.util.*;

class Main {

    public static int n;
    public static int[] d = new int[4]; // 연산자 +, -, *, / 순으로 갯수
    public static int[] number = new int[11]; //숫자 저장

    public static int max = (int) -1e9;
    public static int min = (int) 1e9;

    public static void dfs(int index, int now) {
        if (index == n) {
            max = Math.max(max, now);
            min = Math.min(min, now);
        }
        else {
            if (d[0] > 0) {
                d[0]--;
                dfs(index + 1, now + number[index]);
                d[0]++;
            }
            if (d[1] > 0) {
                d[1]--;
                dfs(index + 1, now - number[index]);
                d[1]++;
            }
            if (d[2] > 0) {
                d[2]--;
                dfs(index + 1, now * number[index]);
                d[2]++;
            }
            if (d[3] > 0) {
                d[3]--;
                dfs(index + 1, now / number[index]);
                d[3]++;
            }
        }
    }

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        for (int i = 0; i < n; i++) {
            number[i] = sc.nextInt();
        }
        for (int i = 0; i < 4; i++) {
            d[i] = sc.nextInt();
        }

        dfs(1, number[0]);

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

처음에 dfs에 대한 아이디어는 있으나 파라미터에 대해 count 하나로만 해결하려 했는데

문제를 발견했다. (연산 결과가 이어지지 않음, 따로 전역 변수로 지정하면 초기화 계속 해야 함.)

 

dfs가 연속될 때 값이 연속적으로 전달되야 하면 파라미터를 통해 전달하자.

 

그리고 무조건 count로 넘기지 않아도 순서가 있는 경우 index로 넘기는 것이 좋다.

(벽을 세우는 경우 순서가 필요하지 않음, 하지만 숫자의 연산의 경우 숫자가 순서대로 들어옴)

 

수정한 소스코드

import java.util.*;

public class Main {

    public static int n;
    public static int add, sub, mul, div;

    public static int[] numbers = new int[11];

    public static int max = (int) -1e9;
    public static int min = (int) 1e9;

    public static void process(int result, int index) {
        if (index == n) {
            max = Math.max(max, result);
            min = Math.min(min, result);
        }

        if (add > 0) {
            add--;
            process(result+numbers[index], index+1);
            add++;
        }
        if (sub > 0) {
            sub--;
            process(result-numbers[index], index+1);
            sub++;
        }
        if (mul > 0) {
            mul--;
            process(result*numbers[index], index+1);
            mul++;
        }
        if (div > 0) {
            div--;
            process(result/numbers[index], index+1);
            div++;
        } 
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            numbers[i] = sc.nextInt();
        }

        add = sc.nextInt();
        sub = sc.nextInt();
        mul = sc.nextInt();
        div = sc.nextInt();

        process(numbers[0], 1);

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

    }
        
}