알고리즘 스터디 - 백준 14888번 : 연산자 끼워넣기

문제 해석

1. N 개의 수로 이루어진 수열
2. 수와 수 사이에 들어갈 수 있는 연산자 +, -, *, // 순으로 총 N-1개
3. 연산자 우위와 관계없이 순서대로 연산을 진행

2개의 수열을 조합하여 만들 수 있는 최대인 것과 최소인 것 구하기

3
3 4 5
1 0 1 0

• • 1개, * 1개가 존재하고 있음

백트래킹

이 문제는 백트래킹 문제로 백트래킹이란? "해를 찾는 도중 더이상 해가 될 수 없는 상태가 되면, 해가 가능한 지점으로 돌아가서 다른 해를 찾아가는 기법"이다.

def 재귀함수(x):
	if 정답이라면? : 
    	정답 출력 또는 저장 등
    else: 정답이 아니라면?
    	for 뻗을 수 있는 모든 자식 노드에 대해서 : 
        	if 정답에 유망하다면:
            	자식노드로 이동
                재귀함수(x+1)
                부모노드로 이동

코드

• 위 형식을 재귀함수로 표현하자면, 아래와 같다.

N = int(input())

num_list = list(map(int, input().split()))
calc_list = list(map(int, input().split()))

max_value = -1e9
min_value = 1e9

def dfs(result, idx):
    if idx == N:
        global max_value
        global min_value
        max_value = max(max_value, result)
        min_value = min(min_value, result)
        return
    for i in range(4):
        if calc_list[i] > 0:
            calc_list[i] -= 1
            if i == 0:
                dfs(result + num_list[idx], idx+1)
            elif i == 1:
                dfs(result - num_list[idx], idx+1)
            elif i == 2:
                dfs(result * num_list[idx], idx+1)
            else:
                dfs(int(result / num_list[idx]), idx+1)
            calc_list[i] += 1
    return
    
dfs(num_list[0], 1)
print(max_value)
print(min_value)