📌난이도🥈1

📌코드

1. 완전탐색-순열

import itertools

N = int(input())
num_list = list(map(int, input().split()))
operator = ['+', '-', '*', '//']
count = list(map(int, input().split()))

# 개수 반영한 연산자 개수
op_list = []
for i, j in zip(operator, count):
    for _ in range(j):
        op_list.append(i)

op_rand = itertools.permutations(op_list, len(op_list))

max = 0
min = 0

for i, op_list in enumerate(op_rand):
    front = num_list[0]

    for num, op in zip(num_list[1:], op_list):

        if op == '+':
            sum = front + num
        elif op == '-':
            sum = front-num
        elif op == '*':
            sum = front*num
        else:
            if front < 0:
                sum = (-front)//num
                sum = -sum
            else:
                sum = front//num

        front = sum

    if i == 0 :
        max = min = front
    else:
        if front > max:
            max = front
        elif front < min:
            min = front

print(max)
print(min)

순열을 사용하면 생성되는 리스트 사이즈도 커지고 반복횟수도 많아져서 비효율적인 것 같다.

2.dfs

def cal(f, b, i):
    if i == 0:
        return f+b
    elif i == 1:
        return f-b
    elif i == 2:
        return f*b
    else:
        if f < 0:
            return -(abs(f) // b)
        else:
            return f//b


def dfs(value, num_list, deph, op_count):
    if deph == N:
        answer.append(value)
        return

    for i, op in enumerate(op_count):  # +:1 , -:0 , *:1 , //:0  ( N-1개 )
        if op > 0:
            op_count[i] -= 1
            sum = cal(value, num_list[deph], i)
            dfs(sum, num_list, deph+1, op_count)
            op_count[i] += 1


N = int(input())
num_list = list(map(int, input().split()))   # 3 4 5
op_count = list(map(int, input().split()))   # 1 0 1 0
answer = []

dfs(num_list[0], num_list, 1, op_count)
print(max(answer))
print(min(answer))

dfs 재귀를 이용해서 1번처럼 모든 경우의 수를 생성하지 않는다.
op_count 는 ['*' , '-' , '*' , '//' ] 를 개수로 받는다. 여기서 enumerate 를 이용해서 i 인덱스를 통해 어떤 문자가 들어갈지를 표현해준다 .
연산자만 바뀔 뿐 숫자들의 위치는 같으므로 deph 를 num_list 의 인덱스처럼 써도 된다.
재귀를 사용하기 때문에 특정 문자가 들어갈 때는 -1 다른 문자가 들어갈 수도 있으므로 재귀 이후에는 +1을 해주어야한다.

3. 신박한 dfs ..???

def dfs(sum, deph, plus, minus, mul, div):
    if deph == N:
        answer.append(sum)
        return

    if plus > 0:
        dfs(sum+num_list[deph], deph+1, plus-1, minus, mul, div)
    if minus > 0:
        dfs(sum-num_list[deph], deph+1, plus, minus-1, mul, div)
    if mul > 0:
        dfs(sum*num_list[deph], deph+1, plus, minus, mul-1, div)
    if div > 0:
        if sum < 0:
            sum = -(abs(sum)//num_list[deph])
        else:
            sum = sum//num_list[deph]

        dfs(sum, deph+1, plus, minus, mul, div-1)


N = int(input())
num_list = list(map(int, input().split()))   # 3 4 5
op_count = list(map(int, input().split()))   # 1 0 1 0
answer = []

dfs(num_list[0], 1, op_count[0], op_count[1], op_count[2], op_count[3])
print(max(answer))
print(min(answer))

📌후기

지금 수준에서 최선은 2번 방법인 것 같다. 기존에 사용하던 dfs방법과 가장 비슷한 방법이었다. 2번과 3번이 dfs 재귀를 사용하기 때문에 결이 같아 보이는데 체감난이도는 3번이 훨씬 높았다.

내가 어렵게 느낀 차이점은 2번은 for 문을 통해 다음 깊이로 들어가는 것을 확인 할수 있고 , for문 때문에 재귀 이후 해줘야하는 작업이 있다는 것을 익숙?하진 않지만 여러번 본적 있지만 ,

하지만 3번은 if문을 통해 재귀에 들어가는데 if-elif-else 가 아니라 for 문 4번 과 같은 효과를 내는 것을 거의 처음 본 것 같다.

재귀를 이렇게 쓸 수도있구나를 느끼기에는 괜찮은 문제인 것 같다.