[DFS] 백준#14502: 연산자 끼워넣기/Python 풀이

📝 문제

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

14888번: 연산자 끼워넣기

💡 접근법

DFS 알고리즘을 활용하여 문제를 해결하였습니다. \(N\)개의 숫자의 순서는 고정입니다. 따라서 DFS 알고리즘으로 모든 연산자 조합으로 연산을 수행하고 연산 결괏값의 최솟값, 최댓값을 구하면 됩니다.

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline

def solve(i, res):
    global ans_max, ans_min
    global add, sub, mul, div
    if i == N:
        ans_max = max(ans_max, res)
        ans_min = min(ans_min, res)
        return
    else:
        if add:
            add -= 1
            solve(i + 1, res + num_list[i])
            add += 1
        if sub:
            sub -= 1
            solve(i+ 1, res - num_list[i])
            sub += 1
        if mul:
            mul -= 1
            solve(i+ 1, res * num_list[i])
            mul += 1
        if div:
            div -= 1
            solve(i + 1, int(res / num_list[i]))
            div += 1

if __name__ == "__main__":
    N = int(input())
    num_list = list(map(int, input().split()))
    add, sub, mul, div = map(int, input().split())
    ans_min = int(1e9)
    ans_max = -int(1e9)
    solve(1, num_list[0])
    print(ans_max)
    print(ans_min)

2) 해설

(1) 라이브러리 import

import sys; input = sys.stdin.readline

• sys 모듈
  • 파이썬 내장 함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.

(2) 연산 함수

def solve(i, res):
    global ans_max, ans_min
    global add, sub, mul, div
    if i == N:
        ans_max = max(ans_max, res)
        ans_min = min(ans_min, res)
        return
    else:
        if add:
            add -= 1
            solve(i + 1, res + num_list[i])
            add += 1
        if sub:
            sub -= 1
            solve(i+ 1, res - num_list[i])
            sub += 1
        if mul:
            mul -= 1
            solve(i+ 1, res * num_list[i])
            mul += 1
        if div:
            div -= 1
            solve(i + 1, int(res / num_list[i]))
            div += 1

연산자 사용 순서에 따라 연산 결과가 달라집니다. 모든 연산 순서를 고려하기 위해 연산자마다 모두 \(if\)문을 사용했습니다. \(if-else\) 구문에 익숙하여 \(if, elif, else\)구문을 사용하면 안 됩니다.

(3) main 함수

if __name__ == "__main__":
    N = int(input())
    num_list = list(map(int, input().split()))
    add, sub, mul, div = map(int, input().split())
    ans_min = int(1e9)
    ans_max = -int(1e9)
    solve(1, num_list[0])
    print(ans_max)
    print(ans_min)

연산 수행 후 최댓값과 최솟값을 구하기 위해 연산 시작 전 초기 최댓값으로 \(-10\)억을, 최솟값으로 \(10\)억을 설정하였습니다.

📝 채점 결과

채점 결과

채점 결과, PyPy3와 Python3 모두에서 패스했습니다. 복잡한 연산은 없기 때문에 PyPy3보다 Python3가 더욱 빠르게 연산했네요 :)

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_14888.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

📚 참고할 만한 포스팅

문제 해결에 사용한 DFS 알고리즘에 대한 자세한 설명은 아래 포스팅을 참고해 주세요!

https://heytech.tistory.com/55

[알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.