백준 14888 - 파이썬

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

이 문제를 보고 어떻게 풀어야 할지 감도 안 잡혀서 바로 다른 사람들의 풀이를 찾아 보았다.

import sys
input = sys.stdin.readline

n = int(input())

nums = list(map(int, input().split()))
op = list(map(int, input().split()))

max_value, min_value = -1e9, 1e9 # 최대값과 최소값을 비교하기 위해 초기값 지정

def dfs(num, idx, add, sub, mul, div):
  global max_value, min_value

  if idx == n: # 깊이가 입력된 길이와 같아질때 max, min 함수 실행
    max_value = max(max_value, num)
    min_value = min(min_value, num)

  # add가 0보다 커야 +연산자가 존재.
  if add > 0:
    # + 연산자이기 때문에 가장 먼저 더해주고, idx+1을 해주며 add-1을 통해 +연산자 하나 줄여줌.
    dfs(num + nums[idx], idx+1, add - 1, sub, mul, div)
  if sub > 0:
    # sub, mul, div도 add와 같음.
    dfs(num - nums[idx], idx + 1, add, sub -1, mul, div)
  if mul > 0:
    dfs(num * nums[idx], idx + 1, add, sub, mul - 1, div)
  if div > 0:
    dfs(int(num / nums[idx]), idx + 1, add, sub, mul, div - 1)

dfs(nums[0], 1, op[0], op[1], op[2], op[3])

print(max_value)
print(min_value)

이 문제를 백트래킹으로 풀 수 있는 이유는 연산자 순서 없이 먼저 입력된 순서대로 연산되기 때문이다. 어찌보면 겁먹지 않고 생각하다보면 스스로 풀 수 있었을지도 모른다. 하지만 요즘 시간이 많이 없기에 조금 생각해보고 모르겠으면 다른 사람의 풀이를 보곤 했다. 이렇게 푸는 방법이 생각의 힘을 기르기에는 부족할 수 있어도, 경험을 쌓기에는 좋은거 같다. 앞으로도 시간이 없을땐 이렇게 풀곤 해야겠다.