BAEKJOON 14888
문제
N개의 수로 이루어진 수열 A1, A2, …, AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.
1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
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
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, …, AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
나의 처음 코드
다른 백트래킹 문제랑 별반 다를 것은 없다. 다만, 주어지는 연산자들의 리스트를 어떻게 이용하느냐. 또한 우리가 생각하는 연산자의 우선순위가 있는게 아니라 순차적 계산이기 때문에 재귀에서 return 했을 때, 기존에 계산한 결과값을 어떻게 변화시키느냐에 따라 다르다. 아, 그리고 이 문제는 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 의 조건과 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다 의 조건이 있으므로, 주의해서 문제를 풀길 바란다.
number_of_num = int(input())
num_list = list(map(int, input().split()))
operand_list = list(map(int, input().split())) # 덧 뺄 곱 나
num_min = 1000000001
num_max = -1000000001
def find_num(depth, result):
global num_min
global num_max
#주어진 연산자들을 다 썼을 경우
if sum(operand_list) == 0:
num_max = result if result > num_max else num_max
num_min = result if num_min > result else num_min
return
for (idx, val) in enumerate(operand_list):
if val == 0:
continue
#쓴 연산자는 갯수에서 뺴준다.
operand_list[idx] -= 1
#return해서 돌아왔을 경우에, 기존의 값을 빼주기 위해서 만든 변수
org_result = result
#처음 시행했을 때는 result 값이 이렇게 된다.
if depth == 0:
if idx == 0:
result = num_list[depth] + num_list[depth + 1]
elif idx == 1:
result = num_list[depth] - num_list[depth + 1]
elif idx == 2:
result = num_list[depth] * num_list[depth + 1]
else:
result = num_list[depth] // num_list[depth + 1]
#그 이후에 시행됐을 경우, 기존의 계산값이랑 다음 정수랑 계산을 해주면 된다.
else:
if idx == 0:
result = result + num_list[depth + 1]
elif idx == 1:
result = result - num_list[depth + 1]
elif idx == 2:
result = result * num_list[depth + 1]
#나누기 경우 C++의 룰을 따라야하므로 적용해주었다.
else:
if result < 0:
result = abs(result) // num_list[depth + 1]
result *= -1
else:
result = result // num_list[depth + 1]
#백트래킹 공통 부분
find_num(depth+1, result)
result = org_result
operand_list[idx] += 1
find_num(0, 0)
print(num_max)
print(num_min)
결과는 맞았습니다. 단, pypy3에서만 통과되고, python에서는 시간초과가 난다. 처음에 최대최소값이 10억인줄 모르고 했다가 틀렸다,,, 문제를 주의해서 읽도록하자…