https://www.acmicpc.net/problem/14888
뭘 어떻게 하라는거야 생각했지만, 그냥 젠틀한 백트래킹이 필요했다. 백트래킹과 DFS 어딘가를 잘 이용하는 영역이라는데, 코드를 보면 이게 어떻게 DFS라고 칠 수 있지라는 생각이 든다. 백트래킹의 비중이 훨씬 높았던 문제.
import sys
numCnt = int(sys.stdin.readline())
numList = list(map(int, sys.stdin.readline().strip().split()))[:numCnt]
operator = list(map(int, sys.stdin.readline().strip().split()))[:4]
maxValue = float('-inf')
minValue = float('inf')
def truncate_division(a, b):
result = a // b
if a % b != 0 and ((a < 0) != (b < 0)): # 음수 방향에서 조정
result += 1
return result
def dfs(totalValue, depth):
global maxValue, minValue
if(depth == (numCnt)):
maxValue = max(totalValue, maxValue)
minValue = min(totalValue, minValue)
else:
for i in range(4):
if(operator[i] > 0):
operator[i] -= 1
if i == 0:
dfs(totalValue + numList[depth], depth + 1)
elif i == 1:
dfs(totalValue - numList[depth], depth + 1)
elif i == 2:
dfs(totalValue * numList[depth], depth + 1)
elif i == 3:
dfs(truncate_division(totalValue, numList[depth]), depth + 1)
operator[i] += 1
dfs(numList[0], 1)
print(maxValue)
print(minValue)
'문제풀이' 카테고리의 다른 글
[PY] 2294 : 동전 2 (1) | 2025.04.01 |
---|---|
[PY] 18352 : 특정 거리의 도시 찾기 (0) | 2025.04.01 |
[PY] <!> 1707 : 이분 그래프 (0) | 2025.04.01 |
[PY] 7569 : 토마토 (0) | 2025.04.01 |
[PY] 2718 : 미로 찾기 (0) | 2025.03.31 |