BOJ 14888 · 연산자 끼워넣기

알고리즘 분류 : 브루트 포스  

재귀 함수를 이용하여 수식 연산의 최댓값과 최솟값을 구하는 문제다.

주어진 연산자를 모두 사용해서 수식을 만들고, 그 수식의 연산 결과를 출력하면 된다. 

• 재귀 함수 종료 조건 : 인덱스가 범위를 넘어선 경우 (index >= N)
• 연산은 각 연산자의 잔여횟수가 1 이상인 경우에 수행한다. 0이면 연산을 수행하지 않는다.
• 연산을 수행한 후, 사용한 연산자의 잔여횟수를 1회 감소시킨다.

---

C++ 소스코드

#include <cstdio>

int n;
int a[11], op[4];
int mx = -1e9, mn = 1e9;

void solve(int index, int ans, int add, int sub, int mul, int div) {
    if (index == n) {
        if (ans > mx) mx = ans;
        if (ans < mn) mn = ans;
        return;
    }
    if (add) solve(index+1, ans+a[index], add-1, sub, mul, div);
    if (sub) solve(index+1, ans-a[index], add, sub-1, mul, div);
    if (mul) solve(index+1, ans*a[index], add, sub, mul-1, div);
    if (div) solve(index+1, ans/a[index], add, sub, mul, div-1);
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    for (int i=0; i<4; i++) scanf("%d", &op[i]);
    solve(1, a[0], op[0], op[1], op[2], op[3]);
    printf("%d\n%d\n", mx, mn);
    return 0;
}

---

Python 3 소스코드

from sys import stdin
input = stdin.readline

n = int(input())
a = list(map(int, input().split()))
op = list(map(int, input().split()))
mx, mn = -1e9, 1e9

def solve(index, ans, add, sub, mul, div):
    global mx, mn
    if index == n:
        mx = max(mx, ans)
        mn = min(mn, ans)
        return
    if add:
        solve(index+1, ans+a[index], add-1, sub, mul, div)
    if sub:
        solve(index+1, ans-a[index], add, sub-1, mul, div)
    if mul:
        solve(index+1, ans*a[index], add, sub, mul-1, div)
    if div:
        solve(index+1, ans//a[index] if ans > 0 else -((-ans)//a[index]), add, sub, mul, div-1)

solve(1, a[0], op[0], op[1], op[2], op[3])
print("{0}\n{1}".format(mx, mn))

✓ 음수를 양수로 나누는 경우, 파이썬과 C++의 방식이 다르다.

✓ 문제 보기에 주어진 내용처럼, 음수를 양수로 바꾼 후 몫을 먼저 구하고, 그 몫을 음수로 다시 바꿔야 한다.

---

참고

• 백준 온라인 저지 : BOJ 14888