백준 14888번 - 연산자 끼워넣기

연산자 끼워넣기 문제 바로 가기

풀이 코드


n = int(input())
numbers= list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
max_value = -10**9
min_value = 10**9
def dfs(current, result, add, sub, mul, div):
    global max_value, min_value
    if current == n:
        max_value = max(max_value, result)
        min_value = min(min_value, result)
        return
    if add > 0: dfs(current+1, result + numbers[current], add-1, sub, mul, div)
    if sub > 0: dfs(current+1, result - numbers[current], add, sub-1, mul, div)
    if mul > 0: dfs(current+1, result * numbers[current], add, sub, mul-1, div)
    if div > 0: dfs(current+1, -((-result)//numbers[current]) if result < 0 else result//numbers[current], add, sub, mul, div-1)

dfs(1,numbers[0], add, sub, mul, div)
print(max_value)
print(min_value)
  

해결 전략

  • dfs함수 인자는 다음과 같다.
    • current: 지금까지 사용한 숫자의 개수 = 다음에 사용할 숫자의 인덱스
    • result: 현재까지 계산된 값
    • add, sub, mul, div: 아직 남아 있는 연산자 개수
  • DFS의 동작 방식
    • 종료 조건 (current == n)
      지금까지 계산된 result가 최종 결과이다. 이를 전역 변수인 max_value와 min_value와 비교해 최댓값과 최솟값을 갱신한다.
    • 현재 단계에서 가능한 모든 연산자 시도하기
      아직 사용 가능한 연산자가 있다면, dfs는 그 연산자를 하나 선택해서 현재 result와 다음 숫자를 연산한 새로운 값을 만들고, 그 상태를 기반으로 다시 dfs를 호출한다.
    • current+1
      “다음 숫자를 사용하러 간다.”는 의미이다.