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

14888번: 연산자 끼워넣기

 

www.acmicpc.net

풀이

단순한 백트래킹 문제이다. 연산자의 갯수에 맞춰서 백트래킹을 해주면 쉽게 해결할 수 있다.

코드

C++

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 10000000000

int n, min_ans = MAX, max_ans = -MAX;
int num[100];
int ops[4];

void dfs(int cnt, int result) {
    if (cnt == n) {
        min_ans = min(min_ans, result);
        max_ans = max(max_ans, result);
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (ops[i] > 0) {
            ops[i]--;
            if (i == 0) dfs(cnt + 1, result + num[cnt]);
            if (i == 1) dfs(cnt + 1, result - num[cnt]);
            if (i == 2) dfs(cnt + 1, result * num[cnt]);
            if (i == 3) dfs(cnt + 1, result / num[cnt]);
            ops[i]++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) cin >> num[i];
    for (int i = 0; i < 4; i++) cin >> ops[i];
    dfs(1, num[0]);
    cout << max_ans << '\n' << min_ans << '\n';
    return 0;
}

Python 3  

import sys

n = int(sys.stdin.readline().rstrip())
nums = list(map(int, sys.stdin.readline().rstrip().split()))
ops = list(map(int, sys.stdin.readline().rstrip().split()))
min_answer = 1e9
max_answer = -1e9


def dfs(idx, result):
    if idx == n:
        global min_answer
        global max_answer
        min_answer = min(min_answer, result)
        max_answer = max(max_answer, result)
        return

    for i in range(4):
        if ops[i] > 0:
            ops[i] -= 1
            if i == 0: dfs(idx + 1, result + nums[idx])
            elif i == 1: dfs(idx + 1, result - nums[idx])
            elif i == 2: dfs(idx + 1, result * nums[idx])
            else: dfs(idx + 1, int(result / nums[idx]))
            ops[i] += 1

dfs(1, nums[0])
print(max_answer)
print(min_answer)