[백준] 14888 연산자 끼워넣기 (실버1) / 백트래킹

문제요약

나의 코드 및 설명

def dfs(count, result):
    if count == len(num_list)-1:
        ans.append(result)
        return

    for i in range(len(op)): #연산을 하나하나 방문하여 돌린다.
        if op[i] != 0: #연산자를 사용할 수 있다면,
            op[i] -= 1 #방문한 연산자의 사용 가능 횟수를 1만큼 줄인다.
            if i == 0:
                dfs(count+1, result + num_list[count+1])
            elif i == 1:
                dfs(count+1, result - num_list[count+1])
            elif i == 2: 
                dfs(count+1, result * num_list[count+1])
            elif i == 3:
                if result < 0: #앞의 값이 음수라면, 문제의 조건에 맞게 양수로 바꿔서 연산 후 음수로 바꿔주기
                    dfs(count+1, -(abs(result) // num_list[count+1]))
                else:
                    dfs(count+1, result // num_list[count+1])
            op[i] += 1 #돌아와서는 방문한 연산자의 사용 가능 횟수를 돌려놓는다.
    

n = int(input())
num_list = list(map(int, input().split()))
op = list(map(int, input().split())) #덧셈, 뺄셈, 곱셈, 나눗셈

ans = []

dfs(0, num_list[0])

print(max(ans))
print(min(ans))

피드백

백트래킹 문제이고 어렵지 않게 풀었다. 백트래킹 문제 연습을 그동안 많이 해서 그런지, 방문체크나 종료조건이 복잡하지 않다면 이런 문제는 어렵지 않게 푸는 것이 가능한 것 같다. 앞으로는 방문체크나 종료조건이 복잡한 문제 위주로 찾아서 연습해야겠다.