[백준 - 15658] 연산자 끼워넣기 (2) [C++]

1. 문제

https://www.acmicpc.net/problem/15658

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

2. 풀이과정

모든 수의 사이에 연산자를 끼워 넣을 수 있는 모든 경우에 대해서 식의 결과의 최대, 최소를 구한다.

[코드설명]

dfs함수는 모든 수의 사이에 연산자를 끼워 넣을 수 있는 모든 경우에 대해 탐색한다.

 

주의해야 할 점은 최대값, 최소값을 저장하는 변수의 초기값을 잘 설정해줘야 하는 것이다.

연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고,

10억보다 작거나 같은 결과가  나오는 입력만 주어지므로

최대값의 초기값은 -10억보다 작은 값,

최소값의 초기값은 10억보다 큰 값으로 설정해줘야한다.

(climits헤더의 INT_MIN, INT_MAX을 사용해도 된다)

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
vector<int> nums;
int opers[4];
int max_v = -1000000010, min_v = 1000000010;


void dfs(int plus, int minus, int multiply, int divide, int ret, int depth) {
    if(depth == n-1) {
        max_v = max(max_v, ret);
        min_v = min(min_v, ret);
        return ;
    }
    if(plus>0) dfs(plus-1, minus, multiply, divide, ret + nums[depth+1], depth+1);
    if(minus>0) dfs(plus, minus-1, multiply, divide, ret - nums[depth+1], depth+1);
    if(multiply>0) dfs(plus, minus, multiply-1, divide, ret * nums[depth+1], depth+1);
    if(divide>0) dfs(plus, minus, multiply, divide-1, ret / nums[depth+1], depth+1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    nums.resize(n);
    for(int i=0; i<n; i++) {
        cin >> nums[i];
    }
    for(int i=0; i<4; i++) {
        cin >> opers[i];
    }
    int ret = nums[0];
    dfs(opers[0], opers[1], opers[2], opers[3], ret, 0);
    cout << max_v << "\n" << min_v;
    return 0;
}