[BOJ/백준 코딩] 연산자 끼워넣기 - PYTHON #14888

소스 코드

# 계산해야하는 숫자의 위치, 현재까지 결과값, 사칙연산 사용 확인
def dfs(idx, temp, check):
    global max_car
    global min_car

    # 탈출조건
    if n == idx:
        if max_car < temp:
            max_car = temp

        if min_car > temp:
            min_car = temp

        return

    for w in range(4):

        # 주어진 사칙연산 개수(?)와 현재까지 사용한 사칙연산 비교
        if check[w] < items[w]:
            if item_detail[w] == '+':
                check[w] += 1
                dfs(idx + 1, temp + numbers[idx], check)
                
                # 이전 상태로 돌리기 위해
                check[w] -= 1

            elif item_detail[w] == '-':
                check[w] += 1
                dfs(idx + 1, temp - numbers[idx], check)
                check[w] -= 1

            elif item_detail[w] == '*':
                check[w] += 1
                dfs(idx + 1, temp * numbers[idx], check)
                check[w] -= 1

            else:
                check[w] += 1
                
                # temp가 음수인 경우
                # numbers에 있는 숫자의 범위는 1 ~ 100이므로 고려 X
                if temp < 0:
                    dfs(idx + 1, -(abs(temp) // numbers[idx]), check)
                    
                # 양수인 경우
                else:
                    dfs(idx + 1, temp // numbers[idx], check)
                check[w] -= 1

    return

n = int(input())

# 계산해야 할 숫자들
numbers = list(map(int,input().split()))

# 사칙연산의 개수
items = list(map(int,input().split()))

# 최대값과 최소값
max_car = -1000000000
min_car = 1000000000

item_detail = ['+','-','*','/']

for q in range(4):
    # 사칙연산이 존재하면
    if items[q] != 0:
        if item_detail[q] == '+':
            dfs(2,numbers[0]+numbers[1],[1,0,0,0])

        elif item_detail[q] == '-':
            dfs(2,numbers[0]-numbers[1],[0,1,0,0])

        elif item_detail[q] == '*':
            dfs(2,numbers[0]*numbers[1],[0,0,1,0])

        else:
            dfs(2,numbers[0]//numbers[1],[0,0,0,1])

print(max_car)
print(min_car)

 

---

해결 방법

1. 처음에는 주어진 사칙연산을 숫자로 인식한 후,(1 = +, 2 = -, 3 = *, 4 = //) for문을 4번 돌면서(시작 값을 다르게 하기 위해) 조합을 만든 후 이를 다시 사칙연산으로 치환해서 문제를 해결하려 함

 

2. 너무 귀찮고, 불필요한 작업이 너무 많다는 생각이 들었음

 

3. 결국 for문을 4번 돌면서(시작 값을 다르게, 가지치기) 백트래킹을 사용

(근데 dfs인지 백트래킹인지 정확히 나누기가 어렵다... 암튼 백트래킹으로 풀려고 생각함)

 

4. 문제에서 나타난 조건만 잘 적용하면 비교적 간단하게 해결이 가능한듯하다

(다만 코드가 깔끔하지는... ㅠㅠ)

---

느낀 점

1. 이 문제는 단 한줄때문에 2번이나 오류가 발생했는데

 

2. max_sum 값을 0으로 준 탓에 문제가 발생했음

(그냥 평소처럼 아무 생각없이 0으로 준 것이 문제)

 

3. 1 2 와 0 1 0 0 이 주어진 경우 최대값(최소값)은 -1(-1)인데 max_sum이 0으로 작성되면 0(-1)이 되버린다 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.