백준[14888] - 연산자 끼워넣기

문제

백준 14888 문제 보기

접근 방법

피연산자에 저장된 +, -, *, / 를 하나씩 적용해 값을 저장한 뒤, 최대값과 최소값을 가려내면 정답을 출력할 수 있다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int num[13];
// + - * /
int op[4];
// 가장 작은 값을 설정
int maxN = -1000000005;
// 가장 큰 값을 설정
int minN = 1000000005;

int dfs(int idx, int amount) {
    if(idx == N) {
        maxN = max(maxN, amount);
        minN = min(minN, amount);
        return 0;
    }

    if(op[0] > 0) {
        op[0] --;
        dfs(idx + 1, amount + num[idx]);
        op[0] ++;
    }
    if(op[1] > 0) {
        op[1] --;
        dfs(idx + 1, amount - num[idx]);
        op[1] ++;
    }
    if(op[2] > 0) {
        op[2] --;
        dfs(idx + 1, amount * num[idx]);
        op[2] ++;
    }
    if(op[3] > 0) {
        op[3] --;
        dfs(idx + 1, amount / num[idx]);
        op[3] ++;
    }
    return 0;
}

int main() {
    cin >> N;
    for(int i = 0; i < N; i ++) {
        cin >> num[i];
    }
    for(int i = 0; i < 4; i ++) {
        cin >> op[i];
    }

    dfs(1, num[0]);
    cout << maxN << "\n";
    cout << minN << "\n";
    return 0;
}