본문 바로가기

Programming/BOJ

BOJ 15658 · 연산자 끼워넣기 (2)


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


BOJ 14888번 '연산자 끼워넣기'와 거의 동일한 문제이다. 바뀐 점은 연산자의 사용 가능 횟수가 증가했다는 점이다. 구현 방법은 이전 문제를 참조.


  • 이전 문제는 연산자의 개수가 최대 N-1개였지만, 이번 문제는 연산자의 개수가 최소 N-1개, 최대 4N개이다.
  • 연산자가 최대로 있는 경우, 연산자를 사용할 때 4개의 연산자 중에서 하나를 선택할 수 있다.
  • 따라서 N-1개의 연산자 자리에 연산자 4개 중 하나를 사용하는 경우이므로, 경우의 수는 4^(N-1) 개이다.
  • N의 최댓값은 11이므로, 최대 경우의 수는 4^10 (약 100만)이다.
  • 따라서 이 문제는 이전 문제와 동일한 코드로 해결할 수 있다.




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))




참고



태그