반응형
알고리즘 분류 : 브루트 포스
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))
참고
반응형