BOJ 14888: 연산자 끼워넣기 [Python 3]

오늘의 문제는 DFS를 통해서 푼 연산자 끼워넣기 문제이다.

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

14888번: 연산자 끼워넣기

n=int(input())
data=list(map(int,input().split()))
cal=list(map(int,input().split()))
answer=[]
visited=[0]*(n-1)
calList=[]
for i in range(4):
    for j in range(cal[i]):
        calList.append(i)
calListOrdered=[]
def dfs(num):
    if num==n-1:
        number=data[0]
        for i in range(n-1):
            if calListOrdered[i]==0:
                number+=data[i+1]
            elif calListOrdered[i]==1:
                number-=data[i+1]
            elif calListOrdered[i]==2:
                number*=data[i+1]
            else:
                number/=data[i+1]
                number=int(number)
        answer.append(number)
        
    for i in range(n-1):
        if not visited[i]:
            visited[i]=1
            calListOrdered.append(calList[i])
            dfs(num+1)
            visited[i]=0
            calListOrdered.pop()

dfs(0)

print(max(answer))
print(min(answer))

data에서 먼저 숫자들을 받고,

cal을 통해서 +,-,*,/  중 몇 각각 몇 개인지 찾는다.

answer는 가능한 정답들을 모두 모으는 list이다.

visited는 dfs를 사용하기 위해서 방문했는지 여부를 확인하는 방법이다.

calList는 cal을 +,-,*,/이 각자 몇개인지를 풀어 써서, 보기 좋게 만들었다. ex) + 3개, - 2개라면 [+,+,+,-,-]

calListOrdered는 calList를 순열로 돌리는 list이다.

 

dfs의 정석적이면서도 복잡한 문제인 것 같다!