BruteForce 문제
이 문제는 N개의 수로 이루어진 수열과 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어져서 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하는 문제이다.
- 이 때 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
ex) 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다.
60가지 식을 만들어서 결과 값을 구한 뒤 최대인 것과 최소인 것을 구하면 된다
아래의 예시에는 최대값이 12이고, 최소값이 1이다!
- 1+2+3-4×5÷6 = 1
- 1÷2+3+4-5×6 = 12
- 1+2÷3×4-5+6 = 5
- 1÷2×3-4+5+6 = 7
예제 입력
3
3 4 5
1 0 1 0예제 출력
35
17문제풀이
- 연산자가 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷) 총 4가지가 이기에 그것에 맞게 if문으로 식을 작성해주면 됨
ex)
N = 3
num = [3, 4, 5]
op = [1, 0, 1, 0]
으로 값이 입력될 때
- 3 + 4 * 5 = 35
- 3 * 4 + 5 = 17
caluculate(1, num[0], op[0], op[1], op[2], op[3])을 실행시켜보면
caluculate(cnt, total, plus, minus, multiply, divide) 함수 안으로 아래와 같은 값이 들어가게 된다.
👉 caluculate(1, 3, 1, 0, 1, 0)
cnt = 1, total = 3, plus = 1, minus = 0, multiply = 1, divide = 0
plus와 multiply이 1이므로
if문을 통해 plus와 multiply를 통과해 실행되어진다.
3 + 4 * 5 = 35
- #1) plus
caluculate(cnt + 1, total + num[cnt], plus - 1, minus, multiply, divide)
3 + 4 = 7
➔caluculate(2 7 0 0 1 0) - #2) multiply
caluculate(cnt + 1, total * num[cnt], plus, minus, multiply - 1, divide)
(3 + 4) * 5 = 35
➔caluculate(3 35 0 0 0 0)
cnt=3이고, N =3이 되어서 if cnt == N: 조건에 걸리게 된다.
그 후
maximum = max(total, maximum) ➔ maximum = max(35, -1ef) ➔ 35
minimum = min(total, minimum) ➔ minimum = min(35, 1ef) ➔ 35
3 * 4 + 5 = 17
- #1) multiply
caluculate(cnt + 1, total * num[cnt], plus, minus, multiply - 1, divide)
3 * 4 = 12
➔caluculate(2 12 1 0 0 0) - #2) plus
caluculate(cnt + 1, total + num[cnt], plus - 1, minus, multiply, divide)
(3 * 4) + 5 = 17
➔caluculate(3 17 0 0 0 0)
cnt=3이고, N =3이 되어서 if cnt == N: 조건에 걸리게 된다.
maximum = max(total, maximum) ➔ maximum = max(17, 35) ➔ 35
minimum = min(total, minimum) ➔ minimum = min(17, 35) ➔ 17
결과
maximum = 35
minimum = 17
전체코드
import sys
input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split())) # +, -, *, //
# 결과값이 최대와 최소를 구해야하므로
# 가장 큰 값에는 maximum = -1e9 -> 이것보다 큰 값이 있으면 교체해주기 위해 가장 작은 값 넣기
# 가장 작은 값에는 minimum = 1e9 -> 작은 값이 있으면 교체 해주기 위해 큰 값 넣기
maximum = -1e9
minimum = 1e9
def caluculate(cnt, total, plus, minus, multiply, divide):
global maximum, minimum
# global : 함수 안에서도 전역변수의 값을 수정할 수 있게 해줌!
if cnt == N:
maximum = max(total, maximum)
minimum = min(total, minimum)
return
if plus:
caluculate(cnt + 1, total + num[cnt], plus - 1, minus, multiply, divide)
if minus:
caluculate(cnt + 1, total - num[cnt], plus, minus - 1, multiply, divide)
if multiply:
caluculate(cnt + 1, total * num[cnt], plus, minus, multiply - 1, divide)
if divide:
caluculate(cnt + 1, int(total / num[cnt]), plus, minus, multiply, divide - 1)
caluculate(1, num[0], op[0], op[1], op[2], op[3])
# 함수 안에서 global을 사용했기 때문에 maximum = -1e9, minimum = 1e9로 출력 되는 것이 아니라
# 바뀐 값이 출력 될 수 있었음!
print(maximum)
print(minimum)