[ BOJ ] 15659 : 연산자 끼워넣기 (3) ( GOLD 4 ) / C

>> 문제 바로가기 (https://www.acmicpc.net/problem/15659)

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 이용해 계산해야 한다. 연산자 우선 순위는 ×와 ÷가 +와 -보다 앞선다. 우선 순위가 같은 경우에는 앞에 있는 식을 먼저 계산한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 3
• 1÷2+3+4-5×6 = -23
• 1+2÷3×4-5+6 = 2
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

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

출력

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

풀이 과정

구현 과정은 https://readytojoin.tistory.com/entry/BOJ-15658-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0-2-SILVER-2-C 와 유사하다.

[ BOJ ] 15658 : 연산자 끼워넣기 (2) ( SILVER 2 ) / C

고려해야 할 점은 식의 계산 과정에서 연산자 우선순위를 이용해야 한다는 점인데, 백트래킹 완성한 식을 처음부터 탐색하면서 곱하기나 나누기가 나온다면 수를 먼저 계산하고, 더하기나 빼기가 나오면 수를 배열에 저장함으로써 곱하기나 나누기를 다 계산하고 더하기와 빼기만 남은 식을 만들도록 한다. 이렇게 계산하고 난 나머지 식은 더하기 빼기를 처음부터 차례대로 적용하며 계산하여 계산 결과를 얻는다.

#include <stdio.h>
int n;
int arr[12];
int ope[4];
int ope_order[11] = {0,};

int max_result = 0;
int min_result = 0;
int first_result = 0;

int compute(void) {
    int waiting_queue[12];
    int waiting_queue_size = 0;
    int waiting_ope_queue[12];
    int waiting_ope_queue_size = 0;

    for (int i = 0; i < n - 1; i++) {
        if (2 <= ope_order[i] && ope_order[i] <= 3) {
            if (waiting_queue_size == 0) {
                if (ope_order[i] == 2) {
                    waiting_queue[waiting_queue_size++] = arr[i] * arr[i+1];
                }
                else {
                    waiting_queue[waiting_queue_size++] = arr[i] / arr[i+1];
                }
            }
            else {
                if (ope_order[i] == 2) waiting_queue[waiting_queue_size - 1] *= arr[i+1];
                else waiting_queue[waiting_queue_size - 1] /= arr[i+1];
            }
        }
        else {
            if (waiting_queue_size == 0) {
                waiting_queue[waiting_queue_size++] = arr[i];
                waiting_queue[waiting_queue_size++] = arr[i+1];
                waiting_ope_queue[waiting_ope_queue_size++] = ope_order[i];
            }
            else {
                waiting_queue[waiting_queue_size++] = arr[i+1];
                waiting_ope_queue[waiting_ope_queue_size++] = ope_order[i];
            }
        }
    }

    int result = 0;
    if (waiting_queue_size == 1) { 
        result = waiting_queue[0];
    }
    else {
        for (int i = 0; i < waiting_queue_size - 1; i++) {
            if (i == 0) {
                if (waiting_ope_queue[0] == 0) {
                    result = waiting_queue[0] + waiting_queue[1];
                }
                else {
                    result = waiting_queue[0] - waiting_queue[1];
                }
            }
            else {
                if (waiting_ope_queue[i] == 0) {
                    result += waiting_queue[i + 1];
                }
                else {
                    result -= waiting_queue[i + 1];
                }
            }
        }
    }

    return result;
}

void backtracking(int now) {
    if (now == n - 1) {
        int result = compute();
        if (first_result == 0) {
            first_result = 1;
            max_result = result;
            min_result = result;
        }
        else {
            if (max_result < result) max_result = result;
            if (min_result > result) min_result = result;
        }
        return;
    }

    for (int o = 0; o < 4; o++) {
        if (ope[o] > 0) {
            ope_order[now] = o; 
            ope[o] -= 1;
            backtracking(now + 1);
            ope[o] += 1;
            ope_order[now] = 0;
        }
    }
}

int main(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    for (int i = 0; i < 4; i++) scanf("%d", &ope[i]);

    backtracking(0);
    printf("%d\n%d", max_result, min_result);
    return 0;
}