백준(BaekJoon) 14888 : 연산자 끼워넣기 c++

▶문제 : 14888번: 연산자 끼워넣기 (acmicpc.net)

14888번: 연산자 끼워넣기

 

▶코드 작성

#include <iostream>
using std::cin;
using std::cout;

int n, min, max;
int num[11];//수열 배열
bool t = false;//min, max의 첫 입력인지 확인

void calculation(int i, int res, int add, int sub, int mul, int div) {
    if (i == n) {//모든 계산을 했다면
        if (t == false) {//첫 입력시
            t = true;
            min = res;
            max = res;
        }
        else if (min > res) min = res;//최솟값
        else if (max < res) max = res;//최댓값
    }
    else {
        if (add > 0) calculation(i + 1, res + num[i], add - 1, sub, mul, div);
        //덧셈을 할 수 있을 때
        if (sub > 0) calculation(i + 1, res - num[i], add, sub - 1, mul, div);
        //뺄셈을 할 수 있을 때
        if (mul > 0) calculation(i + 1, res * num[i], add, sub, mul - 1, div);
        //곱셈을 할 수 있을 때
        if (div > 0) calculation(i + 1, res / num[i], add, sub, mul, div - 1);
        //나눗셈을 할 수 있을 때
    }
}

int main() {
    int add, sub, mul, div;

    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> num[i];
    }
    cin >> add >> sub >> mul >> div;

    calculation(1, num[0], add, sub, mul, div);//num[0]부터 계산 시작

    cout << max << '\n' << min;
}

 

▶해석

n 값의 범위가 작기 때문에 전체 탐색이 가능한 문제이다.

각각 덧셈, 뺄셈, 곱셈, 나눗셈의 남은 횟수를 생각하면서 계산해야 하므로 재귀 함수의 매개변수로 넣어주었다.

또한 min, max의 처음 값에 따라서 잘못된 값을 배출할 수가 있으므로 첫 입력은 무조건 res를 대입하도록 하였다.