[BOJ] 14888. 연산자끼워넣기 - Permutation

[BOJ] 14888. 연산자끼워넣기 - Permutation

제출일 : 2019-10-14

문제 풀이 시간 : 1H

난이도 : ★★☆

Problem

link : https://www.acmicpc.net/problem/148989

Input

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

Output

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

Example

input

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

output

0

Solution & Inpression

최대 10!의 경우의 수가 나오기때문에 완전탐색으로 풀어도 가능한 문제로 순열을 이용하여 해결하였다. 입력이 N개의 숫자에 대해 N-1개의 사칙연산의 개수가 주어지는데 이를 N-1크기의 배열로 값을 받았다.

Code

언어 : JAVA

메모리 : 15,140kb

실행시간 : 352 ms

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

public class Main {
    static boolean[] visit;
    static int[] numbers;
    static int[] op;
    static int n, max, min;

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

        for (int i = 0; i < n; i++)
            numbers[i] = sc.nextInt();

        op = new int[n - 1];
        int idx = 0;
        for (int i = 0; i < 4; i++)
            for (int j = sc.nextInt(); j > 0; j--)
                op[idx++] = i + 1;

        max = Integer.MIN_VALUE;    min = Integer.MAX_VALUE;
        visit = new boolean[n - 1];

        solve(0, 1, numbers[0], 0);
        System.out.println(max);    System.out.println(min);

    }

    public static void solve(int v, int idx, int num, int len) {
        int result = 0;
        if (len == n - 1) {
            if (num > max)    max = num;
            if (num < min)    min = num;
            return;
        }

        for (int i = 0; i < n - 1; i++) {
            if (!visit[i]) {
                visit[i] = true;
                switch (op[i]) {
                case 1:    result = num + numbers[idx];    break;
                case 2:    result = num - numbers[idx];    break;
                case 3:    result = num * numbers[idx];    break;
                case 4:    result = num / numbers[idx];    break;
                }
                solve(i, idx + 1, result, len + 1);
                visit[i] = false;
            }
        }
    }
}