백준 15658 : 연산자 끼워넣기 (2)

문제 링크입니다 https://www.acmicpc.net/problem/15658

15658번: 연산자 끼워넣기 (2)

저번에 풀어봤던 연산자 끼워넣기와 거의 비슷한 문제였습니다. 연산자 끼워넣기에서는 입력으로 주어지는 연산자의 개수가 딱 N - 1개였던 반면에 이번 문제에서는 연산자의 개수가 N - 1개보다 많이 들어오는 상황이었습니다. 재귀 함수를 이용해 모든 경우를 탐색하는 방식으로 문제를 해결했습니다.

 

* solve(idx, cur, plu, min, mul, div)

- idx : 현재 몇 개의 연산자를 골랐는지 확인하는 변수입니다.

- cur : 현재까지 연산한 결과를 누적하며 재귀 함수를 수행합니다.

- plu, min, mul, div : 덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수입니다.

 

 

[소스코드]

 

#include<cstdio>
#include<vector>
using namespace std;
 
int n, m, ans_max, ans_min;
vector <int> a;
 
// idx를 1부터 1씩 증가시키고, cur에 값을 연산한 값을 누적하고, 각 연산자의
// 개수를 1씩 줄여나가면서 n - 1개의 연산자를 골랐다면 
// 최댓값, 최솟값을 update 해주는 함수
void solve(int idx, int cur, int plu, int min, int mul, int div) {
 
    // n - 1개의 연산자를 골랐습니다 정답을 최신화합니다
    if (idx == n) {
        if (ans_max < cur) ans_max = cur;
        if (ans_min > cur) ans_min = cur;
        return;
    }
 
    // 남은 개수가 1개 이상일 때 각 연산자에 해당하는 계산을 수행하며
    // 다음 연산자를 고르러 가는 재귀 함수입니다
    if (plu > 0) solve(idx + 1, cur + a[idx], plu - 1, min, mul, div);
    if (min > 0) solve(idx + 1, cur - a[idx], plu, min - 1, mul, div);
    if (mul > 0) solve(idx + 1, cur * a[idx], plu, min, mul - 1, div);
    if (div > 0) solve(idx + 1, cur / a[idx], plu, min, mul, div - 1);
}
 
int main(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &m);
        a.push_back(m);
    }
    int pl, mi, mu, di;
    scanf("%d%d%d%d", &pl, &mi, &mu, &di);
 
    ans_max = -1000000001, ans_min = 1000000001;
    solve(1, a[0], pl, mi, mu, di);
    printf("%d\n%d", ans_max, ans_min);
    return 0;
}