📖문제

💡입&출력 예시

❓접근

문제를 처음 봤을 때 "사칙연산 규칙을 이용해서 풀어야하나"라는 걱정을 했지만

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다

라는 문제 내용을 봤을 때 예상외로 쉽게 접근 가능할 것 같다는 생각이 들었다.

1. 숫자 값 리스트에 저장
2. 연산자 개수 입력(더하기, 빼기, 곱하기, 나누기 순)
3. 연산자가 나올 수 있는 순열 조합 리스트에 저장
4. 숫자값-연산자-숫자값-연산자-숫자값...이 들어가는 배열 만들기
5. 반복문을 통해 모든 경우의 수 중 최대값과 최소값 구하고 출력

이런 과정을 통해 문제를 풀면 되지 않을까? 라고 생각하고 문제를 풀기 시작했다.

🖥 코드

import itertools
import sys

num = int(sys.stdin.readline())
arr_num = list(map(int, sys.stdin.readline().split()))
arr_cal_num = list(map(int, sys.stdin.readline().split()))

arr_cal = []
arr_cal_cnt = 0
for i in range(4):
    if(arr_cal_num[i] == 0):
        pass
    for j in range(arr_cal_num[i]):
        if(i == 0):
            arr_cal.append('+')
        elif(i == 1):
            arr_cal.append('-')
        elif(i == 2):
            arr_cal.append('*')
        else:
            arr_cal.append('/')
        arr_cal_cnt += 1


arr_case = list(set(itertools.permutations(arr_cal, arr_cal_cnt)))


arr_result = [] #연산자와 숫자가 모두 포함된 함수
for j in range(len(arr_case)):
    cnt_cal = 0
    cnt_num = 0
    arr = []
    for i in range(num+sum(arr_cal_num)):
        if(i % 2 == 0):
            arr.append(arr_num[cnt_num])
            cnt_num+= 1
        else:
            arr.append(arr_case[j][cnt_cal])
            cnt_cal+= 1
    arr_result.append(arr)


max_num = -1e9
min_num = 1e9
for i in range(len(arr_result)):
    sum = arr_result[i][0]
    for j in range(1, num+arr_cal_cnt, 2):
        if(arr_result[i][j] == "+"):
            sum += arr_result[i][j+1]
        elif(arr_result[i][j] == "-"):
            sum -= arr_result[i][j+1]
        elif(arr_result[i][j] == "*"):
            sum *= arr_result[i][j+1]
        else:
            if (sum//arr_result[i][j+1] < 0):
                sum = -(-sum//arr_result[i][j+1])
            else:
                sum = sum//arr_result[i][j+1]

    if(sum > max_num):
        max_num = sum
    if(sum < min_num):
        min_num = sum
print(max_num)
print(min_num)

🍀설명

1. 순열 생성

num = int(sys.stdin.readline())
arr_num = list(map(int, sys.stdin.readline().split()))
arr_cal_num = list(map(int, sys.stdin.readline().split()))

arr_cal = []
arr_cal_cnt = 0
for i in range(4):
    if(arr_cal_num[i] == 0):
        pass
    for j in range(arr_cal_num[i]):
        if(i == 0):
            arr_cal.append('+')
        elif(i == 1):
            arr_cal.append('-')
        elif(i == 2):
            arr_cal.append('*')
        else:
            arr_cal.append('/')
        arr_cal_cnt += 1
        
arr_case = list(set(itertools.permutations(arr_cal, arr_cal_cnt)))

위의 코드를 보면 arr_num 리스트에 수를 저장하고, arr_cal_num 리스트에 + , - , * , /가 몇 개 있는지를 입력받는다.

이를 for문을 통해 arr_cal 리스트에 문자열로 append한다.
저장 후 itertools.permutations(Arr, N)을 사용하여 순열을 만든다

Arr : 순열 만드는 베이스가 되는 리스트
N : 몇 개의 인자로 순열을 만들 것인지를 정하는 수

2. 연산자와 수 합치기

arr_result = [] #연산자와 숫자가 모두 포함된 함수
for j in range(len(arr_case)):
    cnt_cal = 0
    cnt_num = 0
    arr = []
    for i in range(num+sum(arr_cal_num)):
        if(i % 2 == 0):
            arr.append(arr_num[cnt_num])
            cnt_num+= 1
        else:
            arr.append(arr_case[j][cnt_cal])
            cnt_cal+= 1
    arr_result.append(arr)

arr_result 함수에 숫자-연산자-숫자-연산자 순으로 배열에 넣어준다.

3. for문을 통해서 계산식 값 구하기

max_num = -1e9
min_num = 1e9
for i in range(len(arr_result)):
    sum = arr_result[i][0]
    for j in range(1, num+arr_cal_cnt, 2):
        if(arr_result[i][j] == "+"):
            sum += arr_result[i][j+1]
        elif(arr_result[i][j] == "-"):
            sum -= arr_result[i][j+1]
        elif(arr_result[i][j] == "*"):
            sum *= arr_result[i][j+1]
        else:
            if (sum//arr_result[i][j+1] < 0):
                sum = -(-sum//arr_result[i][j+1])
            else:
                sum = sum//arr_result[i][j+1]

    if(sum > max_num):
        max_num = sum
    if(sum < min_num):
        min_num = sum
print(max_num)
print(min_num)

계산식을 구하기 위해 처음 첫 인덱스 값을 sum 변수에 넣어주고 연산자가 배열의 짝수 인덱스에 있는 것을 이용해서 연산자 뒤의 인덱스 값을 연산해주는 방식으로 for문을 돌렸다.

이 때 주의해야할 점이 문제에서

또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.

이 문장을 잘 캐치해야 한다.

코드에서는 이 문장을

        else:
            if (sum//arr_result[i][j+1] < 0):
                sum = -(-sum//arr_result[i][j+1])
            else:
                sum = sum//arr_result[i][j+1]

위 코드와 같이 구현하였다.

💡 백준 제출 결과

브루트포스 알고리즘을 이용해서 문제를 풀어서 그런지 메모리랑 시간을 많이 잡아먹는거 같다🥲🥲