백준 14888번(연산자 끼워넣기) 파이썬

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

14888번: 연산자 끼워넣기

이번 문제는 새로 배운게 많았다.

1. int(1e9)가 10억을 뜻한다는거

2. if, elif가 아닌 if 로만 만들면 전부 다 실행된다는거

 

문제가 생각했던 풀이와 달라 모범답안을 참고하는 수 밖에 없었다. 풀이를 보니 계속 고민을 했어도 못풀었을거 같긴하다 ㅋㅋ;;;

하지만 이렇게 또 새로운 풀이에 대해 배웠으니 뿌듯하긴 하다.

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
sum,sub,mul,div = map(int,input().split())
max_value = -int(1e9) # -10억 -> 비교해줘야하는 수 이기 때문에 10억이 아닌 -10억으로 선언해준다
min_value = int(1e9) # 10억 -> 비교해줘야하는 수 이기 때문에 -10억이 아닌 10억으로 선언해준다


def dfs(sum,sub,mul,div,i,idx):
    global max_value, min_value
    if n == idx: # 모든 수가 다 사용됐을경우
        max_value = max(max_value,i) # 최댓값을 구한다
        min_value = min(min_value,i) # 최솟값을 구한다.
        return
    if sum > 0:
        dfs(sum-1,sub,mul,div,i+a[idx],idx+1)
        
    if sub > 0:
        dfs(sum,sub-1,mul,div,i-a[idx],idx+1)
        
    if mul > 0:
        dfs(sum,sub,mul-1,div,i*a[idx],idx+1)
        
    if div > 0:
        dfs(sum,sub,mul,div-1,int(i/a[idx]),idx+1)
        
dfs(sum,sub,mul,div,a[0],1)

print(max_value)
print(min_value)

백트래킹 좀 어려운 유형의 알고리즘인거 같다. 좀 더 집중적으로 풀어봐야 할 거 같다.