[BOJ] 14888 - 연산자 끼워넣기 (🥈 실버 1티어)

사용 언어: Python3

문제

소수 찾기

풀이

내 풀이

import sys
sys.setrecursionlimit(10**6) # 파이썬에서 DFS(재귀) 사용 시 필수

N = int(input())
lst = list(map(int, input().split()))
operator = list(map(int, input().split())) # 연산자 개수
operator_char = ['+', '-', '*', '//'] # 연산자

mx, mn = -1e9, 1e9
def calc(res): # res는 연산자 식
    global mx, mn
    ret = lst[0]
    for i in range(N-1):
        if res[i] == '+':
            ret += lst[i + 1]
        elif res[i] == '-':
            ret -= lst[i + 1]
        elif res[i] == '*':
            ret *= lst[i + 1]
        else:
            if ret < 0 and lst[i + 1] > 0: # ✅ (음수 // 양수) 인 경우
                ret = -ret // lst[i + 1]
                ret *= -1
            else:
                ret //= lst[i + 1]
    mx = max(mx, ret)
    mn = min(mn, ret)

# ✅ 연산자로만 구성된 연산자 식 만들기
def DFS(L, op_lst): # ✅ op_lst는 사용한 연산자 개수
    if L == N-1:
        calc(res) # ✅ 연산자 계산 후 최대, 최소 갱신
        return
    for i in range(4):
        if operator[i] == 0: # 애초에 없는 연산자
            continue
        if op_lst[i] >= operator[i]: # 해당 연산자 이미 다 쓴 것
            continue
        res[L] = operator_char[i] # ✅ 연산자 캐릭터 넣기
        op_lst[i] += 1 # ✅ 연산자 사용 표시
        DFS(L+1, op_lst)
        res[L] = '' # ✅ 백트래킹
        op_lst[i] -= 1 # ✅ 백틑래킹

res = [''] * (N-1) # 연산자 식 # ex. *+-+
DFS(0, [0,0,0,0])

print(mx, mn, sep='\n')

• 테스트 케이스: 통과
• 제출 결과
  

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기