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

문제 유형

브루트포스, permutation

 

사용 언어

파이썬, C++

 

 

해결의 기본 아이디어

Permutation(순열)을 기본 아이디어로 사용하여 문제를 해결하였다.

파이썬에서는 itertools라는 라이브러리에 permutation함수가 있어 쉽게 해결하였지만, CPP에는 없었기에 클래스 내부에 dfs를 사용하여 Permutation을 구현하였다.

코드

<CPP>

#include <iostream>
#include <vector>

using namespace std;

int cal(int op, int a, int b) {
    if (op == 0)
        return a + b;
    else if (op == 1)
        return a - b;
    else if (op == 2)
        return a * b;
    else
        return a / b;
}

class Perm {
    vector<int> perm;
    vector<int> nums;
    vector<int> tot;
    int n;
public:
    Perm() {
        cin >> n;
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            nums.push_back(tmp);
        }
        for (int i = 0; i < 4; i++) {
            int tmp;
            cin >> tmp;
            for (int j = 0; j < tmp; j++)
                perm.push_back(i);
        }
    }

    void swap(int& a, int& b) {
        int tmp = a;
        a = b;
        b = tmp;
    }

    void perms(int fix) {
        for (int i = fix; i < perm.size(); i++) {
            swap(perm[i], perm[fix]);
            perms(fix+1);
            swap(perm[i], perm[fix]);
        }
        if (fix == perm.size()) {
            int res = nums[0];
            for (int i = 0; i < perm.size(); i++)
                res = cal(perm[i], res, nums[i+1]);
            tot.push_back(res);
        }
    }
    void max_min() {
        int max = tot[0];
        int min = tot[0];
        for (int i = 1; i < tot.size(); i++) {
            if (max < tot[i])
                max = tot[i];
            if (min > tot[i])
                min = tot[i];
        }
        std::cout << int(max) << std::endl;
        std::cout << int(min) << std::endl;
    }
    void result() {
        perms(0);
        max_min();
    }
};

int main() {
    Perm p;
    p.result();
    return 0;
}

<Python>

import itertools

def cal(op, a, b):
	if op == 0:
		return a + b
	elif op == 1:
		return a - b
	elif op == 2:
		return a * b
	else:
		return a // b if a > 0 else -(-a // b)


n=int(input())
nums = list(map(int, input().split()))
ops=[]
for idx, i in enumerate(map(int, input().split())):
	ops.extend([idx]*i)
# visit=[False for _ in range(len(ops))]
tot=set()


for perm in set(itertools.permutations(ops, len(ops))):
	res = nums[0]
	for idx, p in enumerate(perm):
		res=cal(p,res,nums[idx+1])
	tot.add(res)
print(max(tot))
print(min(tot))