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

 

 

n = int(input())
data = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

max_val = -1e9
min_val = 1e9


def dfs(i, total, add, sub, mul, div):

    global max_val, min_val

    if n == i:
        max_val = max(max_val, total)
        min_val = min(min_val, total)
        return

    else:
        if add > 0:
            dfs(i + 1, total + data[i], add - 1, sub, mul, div)
        if sub > 0:
            dfs(i + 1, total - data[i], add, sub - 1, mul, div)
        if mul > 0:
            dfs(i + 1, total * data[i], add, sub, mul - 1, div)
        if div > 0:
            dfs(i + 1, int(total / data[i]), add, sub, mul, div - 1)


dfs(1, data[0], add, sub, mul, div)
print(max_val)
print(min_val)

1.n에 수의 개수를 입력

2.data는 두번째 열에 수열을 입력하여 list에 저장

3.add,sub,mul,div 는 연산자를 입력받음

4.max_val,min_val 는 -10억-10억

5.dfs로 전개

6.i=1부터 시작하며 n(수의 개수)와 동일할 경우 max,min값을 구하여 종료

7.add,sub,mul,div 각각 0보다 크면..즉 1이상이면, dfs함수를 돈다.(재귀)

8.dfs(1,data[0],add,sub,mul,div)

는 첫번째 n=1, data[0] 즉 0번째 숫자로 초기값을 두고,

n ,data[n-1]부터 1씩 더해간다.

 

 백트래킹, dfs문제이다.

dfs를 처음 접하는 분은 이해하기가 엄청 오래걸린다.

한참 생각하고, 대입하고, 이제야 좀 감이 온다.

문제보고 풀다가 못 풀어서 구글링해서 풀었다.

언젠가 코딩쉽게 하는 날이 오겠지...