백준 14888 풀이 (재귀함수, 백트래킹, 연산자 끼워넣기)

일단 혹시나 내 코드를 보시는 분은 내가 아직도 백트래킹을 이해를 못한 관계로 코드만 참고하면 좋겠다.

일단 한방에 성공하긴 했으나 아직도 재귀와 백트래킹이 두려운 시점이라 일단 재귀로 대충짜봤다.

 

1. 주어진 값들을 리스트와 연산자 맵을 재귀함수로 사용한다.

2. 리스트의 0번째와 1번째를 연산자 맵에서 하나꺼내서 사용한다.

3. 반복하다가 연산자 맵이 전부 0이면(sum이 0이면) 종료하고 전체 리스트에 넣어준다.

n = int(input())

nlist = list(map(int,input().split()))
Map = list(map(int,input().split()))
Tmp = []

def back(nlist, miniMap):
    if len(nlist) == 1:
        Tmp.append(nlist[0])
        return
    
    for op in range(4):
        if miniMap[op] < 1:
            continue
        else:
            a = nlist[0]
            b = nlist[1]
            if op == 0:
                c = [a + b] + nlist[2:]
            elif op == 1:
                c = [a - b] + nlist[2:]
            elif op == 2:
                c = [a * b] + nlist[2:]
            else:
                if a < 0: #음수인경우
                    c = [-(abs(a)//b)] + nlist[2:]
                else:
                    c = [a//b] + nlist[2:]
            miniMap[op] -= 1
            back(c,miniMap)
            miniMap[op] += 1
back(nlist, Map)
print(max(Tmp))
print(min(Tmp))

 

pypy3를 사용하라고 하는거 같아서 pypy3로 제출했다.