[백준 14888] 연산자 끼워넣기

[BanApp]

pypy3

import sys
import itertools
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split())) #숫자 배열 받기
c = list(map(int,sys.stdin.readline().split())) #연산 기호 개수 받기
g = [] #연산기호를 실제로 추가할 리스트

for j in range(len(c)):
    for i in range(c[j]):
        if j == 0:
            g.append('+')
        elif j == 1:
            g.append('-')
        elif j == 2:
            g.append('*')
        elif j == 3:
            g.append('/')
            
nPr = list(itertools.permutations(g, n-1)) #n-1개의 원소를 가지는 조합 리스트 생성

max = -1000000000
min = 1000000000
ans = 0


for i in nPr:
    ans = arr[0]
    for j in range(len(i)):
        if i[j] == '+':
            ans = ans + arr[j + 1]

        elif i[j] == '-':
            ans = ans - arr[j + 1]

        elif i[j] == '*':
            ans = ans * arr[j + 1]

        elif i[j] == '/':
            if ans > 0:
                ans = ans // arr[j + 1]
            elif ans < 0:
                ans = -(abs(ans) // arr[j + 1])

    if ans > max:
        max = ans

    if ans < min:
        min = ans

print(max)
print(min)

다른 스터디분이 올린걸 보고 궁금해서 나도 풀어봤다.
솔직히 파이썬으로 풀어서 풀었지 다른 언어로 했으면 상당히 난해(?)했을것 같다.
풀면서 2학년때 자료구조 과제로 했던 계산기 만드는 문제가 떠올랐다..
나는 단순히 브루트포스 방식으로 풀었다.
문제에서 n의 최대값을 더 크게 제한했거나 하면 브루트포스로 풀지 못하는 문제가 될 것이다.
입력받은 연산기호의 숫자들을 리스트에 일단 다 넣었다.
그리고 편법을 사용했는데 파이썬에서 기본적으로 제공하는 permutations 라는 순열을 만들어주는 함수가있다.
남는거 없이 연산기호를 모두 사용하므로 g 리스트에서 n-1개의 원소를 갖는 순열 조합을 모두 리스트 형태로 만들어서 nPr 리스트에 넣어준다.
이제 해당리스트를 반복문을 돌면서 연산기호에 맞게 연산을 해준다.
max는 만들어질 수 있는 가장 최소값으로 초기화, min은 만들어질 수 있는 가장 최대값으로 초기화 해주면 이것 때문에 발생하는 오류는 피할 수 있다.
파이썬하고 c++ 음수 나누기 표준이 조금 다른것 같아서 절댓값을 씌우고 나누고 다시 음수로 바꿔주는 절차를 넣어 주었다.
결과적으로 연산된 ans가 기존 max 값보다 크면 max를 ans로 바꾼다.
ans가 기존 min 값보다 작으면 min을 ans로 바꾼다.
여기서 재수없게 ans == min == max 값이 되는 불상사를 피하기 위해서 위에 max, min을 초기화 했다.
결과적으로 max, min 값을 출력하면 정답!
근데 위 코드로 pypy3에서 정말 겨우겨우 통과하는 것 같다.
python3로 돌리면 시간초과가 뜬다..
더 최적화 시킬 아이디어 댓글 부탁드립니다...ㅠㅠ

[ghdcksgml1]

제 느낌상으로 _nP_r 함수의 속도가 매우 느릴 것으로 예상됩니다.

백트래킹을 공부하시면 _nP_r과 _nC_r을 빠르게 구현할 수 있습니다.

https://github.com/ghdcksgml1/Algorithm_Study/tree/main/12_%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

N과 M 시리즈 싹다 풀면 백트래킹 고수가 될 수 있습니다.

[BanApp]

백트래킹으로 다시 풀어보겠습니다..!
permutations함수는 시간복잡도가 o(n!) 이라는 정신나간 시간복잡도를 갖고 있었습니다.