글 읽기 - PyPy3로 겨우 통과했는데 다른정답에 비해 메모리, 시간이 왜이렇게 큰가요?

black01676 1년 전 0

DFS로 연산자들의 조합을 싹 구한 후 계산을 해서 Min, Max를 구했습니다 ㅠㅠ

DFS를 사용했다면 비슷한 시간 복잡도를 가질것같은데

제출 후 결과를 보면 다른분들에 비해 시간, 메모리가 너무 큽니다.

(심지어 제 답안은 Python으로는 시간초과 뜹니다)

고수님들 가르침 부탁드립니다!!

import sys
input = sys.stdin.readline

N = int(input().strip())
num = list(map(int, input().split()))
temp = list(map(int, input().split()))
op = ['+']*temp[0]+['-']*temp[1]+['*']*temp[2]+['/']*temp[3]

def dfs (arr) :
    global num, Max, Min, visit

    if len(arr)==N-1 :  #계산하기
        result = num[0]
        for i in range(N-1) :
            if arr[i] == '+' :
                result += num[i+1]
            elif arr[i] == '-' :
                result -= num[i+1]
            elif arr[i] == '*' :
                result *= num[i+1]
            elif arr[i] == '/' :
                result = int(result/(num[i+1]))
        if Max < result :
            Max = result
        if Min > result :
            Min = result
        return
    for i in range(len(op)) :
        if visit[i] == True :
            continue
        arr.append(op[i])
        visit[i] = True
        dfs(arr)
        arr.pop()
        visit[i] = False

Min = 10e9
Max = -10e9
visit = [False]*(N-1)
dfs([])
print (Max, Min)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

PyPy3로 겨우 통과했는데 다른정답에 비해 메모리, 시간이 왜이렇게 큰가요?

black01676 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말