[백준] 14888. 연산자 끼워넣기

문제 링크

[백준] 14888. 연산자 끼워넣기

풀이 과정

1달 전에 수열을 완성후 결과를 계산해서 풀었습니다.

이전에 풀었던 방법이 아닌 어제 [SWEA] 4008. 숫자 만들기의 해결방법인 재귀 함수가 결과값을 누적해서 들고 다니는 방식으로 풀었습니다.

수열을 완성하고 식을 계산하는 것보다 시간이 반으로 단축되는 것을 확인할 수 있었습니다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N;
    static int[] operand;
    static int[] operator;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        operand = new int[N];
        for (int i = 0; i < N; i++)
            operand[i] = sc.nextInt();
        operator = new int[4];
        for (int i = 0; i < 4; i++)
            operator[i] = sc.nextInt();

        solve(1, operand[0]);

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

    private static void solve(int depth, int sum) {
        if (depth == N) {
            max = Math.max(max, sum);
            min = Math.min(min, sum);

            return;
        }

        for (int i = 0; i < 4; i++) {
            if (operator[i] == 0) continue;

            operator[i]--;
            switch (i) {
                case 0:
                    solve(depth + 1, sum + operand[depth]);
                    break;
                case 1:
                    solve(depth + 1, sum - operand[depth]);
                    break;
                case 2:
                    solve(depth + 1, sum * operand[depth]);
                    break;
                case 3:
                    solve(depth + 1, sum / operand[depth]);
                    break;
            }
            operator[i]++;
        }
    }
}