백준 C++ 14888번) 연산자 끼워넣기

사용언어 ) C++

백준 : https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

문제)

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

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

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

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

 

풀이)

  이 문제는 백트래킹이라는 기법을 사용하여 해결하면 된다. 백트래킹이라 함은, 모든 가능한 수를 재귀 함수를 통해서 파악하는 방식이다. 

아래의 코드를 해석하면 Calc 이라는 함수를 통해서 백트래킹 알고리즘이 실행되고, 먼저 +연산자부터 시작하여 /까지 실행된다. 그 와중에 모든 가능한 수를 파악하기 위해서 하나의 연산식이 끝나면 재귀 함수가 돌아오면서 사용한 연산자를 다시 채워 넣는다.

 

사용 코드

#pragma warning(disable:4996)
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
vector<int> num;
int op[4] = { 0 };
ll mins = 1000000000;
ll maxs = -1000000000;
int N;
void Calc(int i, int result) { 
    if (N == i) {
        if (mins > result) {
            mins = result;
        }
        if (maxs < result) {
            maxs = result;
        }
        return;
    }
    if (op[0] != 0) {
        op[0] -= 1;
        int ns = result + num[i];
        Calc(i + 1, ns);
        op[0]++;
    }if (op[1] !=  0) {
        op[1] -= 1;
        int ns = result - num[i];
        Calc(i + 1, ns);
        op[1]++;
    }
    if (op[2] != 0) {
        op[2] -= 1;
        int ns = result * num[i];
        Calc(i + 1, ns);
        op[2]++;
    }
    if (op[3] != 0) {
        op[3] -= 1;
        int ns = result / num[i];
        Calc(i + 1, ns);
        op[3]++;
    }
}

int main() {
    int n;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &n);
        num.push_back(n);
    }
    for (int i = 0; i < 4; i++) {
        scanf("%d", &n);
        op[i] = n;
    }
    Calc(1, num[0]);
    cout << maxs << "\n" << mins << "\n";
}