백준 15658번 연산자 끼워넣기 2

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

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

풀이

브루트 포스 문제입니다!

문제 난이도에 비해 생각보다 쉽지 않아서 많이 고전했던 문제이다.

이 문제는 개인적으로는 그 전 시리즈 문제 (BOJ 14888번 연산자 끼워넣기 https://www.acmicpc.net/problem/14888) 

보다 어렵다고 생각했는데 아마 브루트 포스에 익숙치 않아서 그런것 같다.

이 문제도 일반적인 bfs처럼 가지치기가 필요한데 최소경로로 하는 것이 아니기 때문에 모든 경우를 다 해보는 브루트 포스를 이용하고자 한다.

이 문제에서 연산의 경우의 수는 총 4가지이며 각각 '+','-','*','/' 이다.

(참고로, 연산의 가짓수가 최대 44개까지 존재하므로 수열을 통해 이 문제를 해결할 수 없지만 답에 들어갈 연산자는 n-1개 이므로 브루트 포스로 해결가능하다!)

각각이 몇 개 씩인지 고정되어있지 않기 때문에 이 문자를 다 쓸때까지 연산을 사용하고 이후에 사용한 연산의 개수가 N-1일 때 그 값을 리턴한 후 최대, 최소랑 비교하면된다.

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
 
 
pair<int, int> calc(vector<int> &a, int idx, int cur, int plus, int minus, int mul, int div) {
    int n = a.size();
    if (idx == n) return make_pair(cur, cur);
    vector<pair<int, int> >res;
    if (plus > 0) {
        res.push_back(calc(a, idx + 1, cur+a[idx], plus - 1, minus, mul, div));
    }
    if (minus > 0) {
        res.push_back(calc(a, idx + 1, cur - a[idx], plus, minus - 1, mul, div));
    }
    if (mul > 0) {
        res.push_back(calc(a, idx + 1, cur * a[idx], plus, minus, mul - 1, div));
    }
    if (div > 0) {
        res.push_back(calc(a, idx + 1, cur / a[idx], plus, minus, mul, div - 1));
    }
    auto ans = res[0];
    for (auto p : res) {
        if (ans.first < p.first) {
            ans.first = p.first;
        }
        if (ans.second > p.second) {
            ans.second = p.second;
        }
    }
    return ans;
}
int main() {
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int plus, minus, mul, div;
    scanf("%d %d %d %d", &plus, &minus, &mul, &div);
    auto p = calc(a, 1, a[0], plus, minus, mul, div);
    cout << p.first << "\n";
    cout << p.second;
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~