백준 14888
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하기.
- N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
- 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
- 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.
입출력
| 입력 | 출력 |
|---|---|
| 2 5 6 0 0 1 0 | 30 30 |
| 3 3 4 5 1 0 1 0 | 35 17 |
| 6 1 2 3 4 5 6 2 1 1 1 | 54 -24 |
접근 방식
: permutations 사용해서 가능한 연산자 집합 나열. set으로 중복 제거.
알게된 점
방법1. permutations를 활용하여 모든 경우의 수 구하기
-> 시간 오래걸림
방법2. 재귀를 활용하여 모든 경우의 수 고려하기(백트래킹)
코드
permutations 방식
from itertools import permutations
n = int(input())
nums = list(map(int, input().split()))
cals = list(map(int, input().split()))
c = ['+', '-', '*', '/']
calList = []
for i in range(4):
for j in range(cals[i]):
calList.append(c[i])
a = list(set(permutations(calList, len(calList))))
ans = []
for ca in a:
result = nums[0]
for i in range(len(ca)):
if ca[i] == '+':
result += nums[i+1]
elif ca[i] == '-':
result -= nums[i+1]
elif ca[i] == '*':
result *= nums[i+1]
elif ca[i] == '/':
if result//nums[i+1] < 0:
result = -(-result//nums[i+1])
else:
result = result//nums[i+1]
ans.append(result)
print(max(ans))
print(min(ans))
backtracking 방식
n = int(input())
nums = list(map(int, input().split())) # 순서 바꿀 수 없음
oper = list(map(int, input().split())) # 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수
def cal(i, ans, p, m, mul, div):
global max_ans, min_ans
if i==n:
max_ans = max(ans, max_ans)
min_ans = min(ans, min_ans)
return
if p > 0:
cal(i+1, ans+nums[i], p-1, m, mul, div)
if m > 0:
cal(i+1, ans-nums[i], p, m-1, mul, div)
if mul > 0:
cal(i+1, ans*nums[i], p, m, mul-1, div)
if div > 0:
cal(i+1, int(ans/nums[i]), p, m, mul, div-1)
max_ans = -1e9
min_ans = 1e9
cal(1, nums[0], oper[0], oper[1], oper[2], oper[3])
print(max_ans, min_ans)
int(ans/nums[i])로 하는 이유는,
파이썬에서 만약 -6 // 4를 하면 몫이 -1이 아닌 -2가 나오기 때문이다.
4*(-2)+2 = -6 이런식으로 만족시키기 위해 설계되어있기 때문에,
몫을 구하는 것이 아닌 나누기를 해서 나머지를 버리는 방식으로 가야한다.
int함수를 써주면 소수부를 버리고 정수부를 남긴다.
