코딩테스트 스터디-14888 연산자 끼워넣기

ACMICPC 14888 단어 수학

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다.  
또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다.  
연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다.  
이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고,  
주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는  
총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.  
또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의  
기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.  
이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7
N개의 수와 N-1개의 연산자가 주어졌을 때,  
만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

첫번째 풀이

처음에는 그냥 막 풀었다.

이 막 푼다는 것이, 연산자를 전부 목록에 저장해놓은 다음

파이썬의 itertools.permutations(순열) 기능을 사용해

모든 순서를 구해서 각각 계산한 다음 최대 최소값을 없데이트 하는 것이다.

정말 간단하죠~?

첫번째 정답

아래는 파이썬으로 작성한 코드~

from itertools import permutations

n = int(input())

su = list(map(int,input().split()))

# 0번은 더하기, 1번은 빼기, 2번은 곱하기, 3번은 나누기
yonsanja = list(map(int,input().split()))



def solution(su,yonsanja):
    #최대 최소값 초기화(-10억~10억까지라 했으니까)
    choidae = -1000000000
    choiso = 1000000000

    #무작정 풀기: 일단 연산자 리스트에 저장
    tosso = []
    for i in range(yonsanja[0]):
        tosso.append('+')
    for i in range(yonsanja[1]):
        tosso.append('-')
    for i in range(yonsanja[2]):
        tosso.append('*')
    for i in range(yonsanja[3]):
        tosso.append('/')

    #이 연산자 리스트를 순열화해서 최대/최소 계산
    for i in permutations(tosso,len(tosso)):
        ee = su[0] #일단 첫번째 수부터 시작해서...
        index = 1 #다음 인덱스의 수를 계산하는 식으로
        for j in i:
            if j=='+':
                ee+=su[index]
            elif j=='-':
                ee-=su[index]
            elif j=='*':
                ee*=su[index]
            elif j=='/':
                #C++14식 나누기 적용
                if ee<0 and su[index]>0:
                    ee = -ee
                    ee = ee//su[index]
                    ee = -ee
                else:
                    ee = ee//su[index]
            index+=1 # 다음 수로: 수의 개수는 연산자보다 무조건 1개 많기 때문에 인덱스 오류가 나지 않아
        # 최대,최소값 갱신
        choiso = min(ee,choiso)
        choidae = max(ee,choidae)
    return choidae, choiso

result = solution(su,yonsanja)
print(result[0])
print(result[1])

두번째 풀이

그런데 이렇게 푸니까 통과는 했는데…시간이 많이 걸렸다.

그런데 당직이 2년 전 똑똑했던 시절(?)에 풀었던 게 있지 않았는가! 지금 코드보다 두배나 빠르고, 메모리도 1/3밖에 잡아먹지 않았다!!

반성하자

당시에는 문제를 bfs로 풀었던 것으로 보여 다시 분석해 보았다.

• 일단 최대/최소값 초기화까지는 동일하고…
• 연산자 리스트를 그대로 사용한다. 이게 어떻게 이루어지냐 하면…
• dfs의 원리를 사용한다 했으니, 각 연산자를 순서대로 탐색해…
• 연산에 맞게 계산하고, 최대/최소값을 업데이트 하고..
• 해당 연산자의 값을 -1 뺀 다음 재귀를 돈다. 그러면 다음에는 또 더하기-뺄셈-곱셈-나누기 순으로 재귀가 돌 것이다.
  • 여기서 deepcopy를 사용해서 각 재귀함수에 인자로 주는 연산자 리스트가 겹치지 않게 하는 것이 핵심~
  • 만약 더하기가 없으면 빼기부터 돌 것이고, 더하기 재귀를 모두 돌았으면 다음 for문인 빼기부터 시작할 것이니…
• 이렇게 돌다 보면 결국은 모든 경우의 수가 다 계산되는 것이다!

두번째 정답

아래는 파이썬으로 작성한 코드~

from copy import deepcopy

n = int(input())
su = list(map(int,input().split()))
yon = list(map(int,input().split()))

mmax = -1000000000
mmin = 1000000000
def dfs(hap,su,yon,count):
    global mmax,mmin
    kijun = hap
    if count==n:
        if hap>mmax:
            mmax = hap
        if hap<mmin:
            mmin = hap
        return
    for i in range(len(yon)):
        hap = kijun
        yona = deepcopy(yon)
        if yon[i]!=0:
            if i==0:
                hap+=su[count]
                yona[i]-=1
                dfs(hap,su,yona,count+1)
            elif i==1:
                hap-=su[count]
                yona[i]-=1
                dfs(hap,su,yona,count+1)
            elif i==2:
                hap*=su[count]
                yona[i]-=1
                dfs(hap,su,yona,count+1)
            elif i==3:
                if hap<0:
                    hap=-((-hap)//su[count])
                else:
                    hap//=su[count]
                yona[i]-=1
                dfs(hap,su,yona,count+1)

dfs(su[0],su,yon,1)

print(mmax)
print(mmin)

후기

이번 경우는 두 가지 경우로 풀어보았기 때문에 올려보았다.
dfs를 통해 순열 문제를 해결할 수 있다니!