[삼성SW역량][Python/BOJ] 백준 14888 연산자 끼워넣기(DFS)

 

 

 

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

14888번: 연산자 끼워넣기

 

 

 

 

 

dfs(idx,val) : val 이 기존 값 , idx는 이제 더할 값의 인덱스 

다음 dfs는 val에 idx인덱스의 값을 (더하거나 ,빼거나 곱하거나 나눠주고) idx를 1 증가시킨다.) 

 

 

그래서 처음에 dfs(1, numbers[0]) 를 호출해주는 것이다. 

numbers[0]을 가장 초기값으로 idx가 1인 값을 선택된 기호로 계산하여 val 에 저장하기 때문이다. 

 

 

💻 코드 : 

n = int(input())
numbers = list(map(int,input().split()))
oper = list(map(int,input().split()))
answer = []

def dfs(idx,val) :
    if idx == len(numbers) :
        answer.append(val)
        return 
    for i in range(len(oper)) :
        if oper[i] >= 1 :
        	# 사용했음을 알림 
            oper[i] -= 1 
            if i == 0:
                dfs(idx+1 , val+numbers[idx])
            elif i == 1 :
                dfs(idx+1 , val-numbers[idx])
            elif i == 2 :
                dfs(idx+1 , val*numbers[idx])
            else :
                if numbers[idx]!= 0 :
                    if val <0 : 
                        dfs(idx+1 , -(-val//numbers[idx]))
                    else :
                        dfs(idx+1 , val//numbers[idx])
            # 다시 되돌려준다. 
            oper[i]+=1 
            
dfs(1,numbers[0])
print(max(answer))
print(min(answer))

 

 

 

 

참고 블로그 : 

 

https://hongcoding.tistory.com/119

[백준] 14888 연산자 끼워넣기 (Python 파이썬)

 

복습 : 

✅ 20220701

✅ 20220915