본문 바로가기

Programming/BOJ

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++의 방식이 다르다.

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




참고



태그