둘은 다르다. 어떻게 다르고 왜 다를까?
https://www.acmicpc.net/problem/14888
14888 연산자 끼워넣기
import sys
from itertools import permutations
from collections import Counter
n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
operators = list(map(int, sys.stdin.readline().split()))
ops = []
for i in range(len(operators)):
if operators[i] != 0:
for _ in range(operators[i]):
ops.append(i)
counter = Counter(ops)
def backtrack(path, counter, perm):
if len(path) == n-1:
perm.append(path.copy())
return
for op in counter:
if counter[op] > 0:
counter[op] -= 1
path.append(op)
backtrack(path, counter, perm)
path.pop()
counter[op] += 1
def solve(path):
mini = 10 ** 9
maxi = - 10 ** 9
for case in path:
result = numbers[0]
for i in range(len(case)):
if case[i] == 0:
result += numbers[i+1]
elif case[i] == 1:
result -= numbers[i+1]
elif case[i] == 2:
result *= numbers[i+1]
elif case[i] == 3:
result = int(result / numbers[i+1])
if int(result) < mini: mini = int(result)
if int(result) > maxi: maxi = int(result)
return (mini, maxi)
perm = []
backtrack([], counter, perm)
mini, maxi = solve(perm)
print(int(maxi))
print(int(mini))수정할 때마다 그냥 덕지덕지 붙인 거라 별로 좋은 풀이는 아니지만... 일단 문제를 해결하기 위한 마지막 반례가 이곳에 있었다. result = int(result / numbers[i+1])
음수 나눗셈을 처리해야 하길래, 원래는 아래처럼 구현했다.
다 풀고 보니 약간 바보같네...
그냥 a // b로 풀면 예제 3번의 최댓값 부분이 잘못 계산된다.
1 - 2 = -1
-1 // 3 = -1
-1 + 4 = 3
3 + 5 = 8
8 * 6 = 48
원래는 54가 되어야 한다.
-1/3이 0이 되면 이 문제에서 원하는 답을 구할 수 있다.
a//b와 a/b
- a//b는 정수 나눗셈 (floor division)
- 나눗셈 결과를 내림 (바닥 함수에 넣음, floor)
- -1 // 3은, -1/3이지만, 값을 내려서 정수로 만들기 때문에 -1/3보다 작은 수 중에 가장 큰 정수인 -1이 된다.
- a/b는 실수 나눗셈
- 일반적인 실수 나눗셈을 수행한다. -1/3은 -0.33333... 이 된다.
- int(a/b)하면, int(-1/3)이 되고, 단순히 소수점 이하를 버리면서 0이 된다.
a//b와 int(a/b)는 다르고... 이 문제에서는 a/b를 사용해야 했음을 예제 3으로부터 알 수가 있다.
a//b는 floor division이라는 것을 기억하자~
백트래킹 구현이 손에 잘 안 익네
