글 읽기 - python 시간초과 질문입니다

ksungyoun 2년 전 0

제가 혼자 DFS를 공부하고있는데요.

처음으로 문제를 풀었다고 생각했는데 안타깝게도 시간초과가 뜨네요 (퍼센트도 안올라감)ㅜㅜ

혹시 어느 부분이 문제인지 알려주실 고수형님 계신가요? ㅠㅠ

import sys


def dfs(n):
    global minNum
    global maxNum
    global number1
    if n == N - 1:
        k = result[:]
        if k not in combi:
            combi.append(k)
            number1 = int(cal2(A, k))
        if minNum > number1:
            minNum = number1
        if maxNum < number1:
            maxNum = number1
        return
        
    for i in range(N - 1):
        if visited[i]:
            continue
        visited[i] = True
        result.append(oper2[i])
        dfs(n + 1)
        result.pop()
        visited[i] = False


def cal2(A, k):
    string = '{}'.format((A[0]))
    for i in range(1, N):  # str="("+str+'{}'.format(k[i-1])+'{}'.format(A[i])+")"
        if int(string) < 0 and k[i - 1] == "//":
            string = str(abs(int(string)))
            string = "(" + string + '{}'.format(k[i - 1]) + '{}'.format(A[i]) + ")"
            string = str(-eval(string))
            continue
        string = "(" + string + '{}'.format(k[i - 1]) + '{}'.format(A[i]) + ")"
        string = str(eval(string))
    return string

if __name__ == "__main__":
    maxNum = -1e10
    minNum = 1e10
    count = 0
    N = int(sys.stdin.readline())  # number
    A = list(map(int, sys.stdin.readline().split()))  # integer
    oper = list(map(int, sys.stdin.readline().split()))  # + - x / = 0 1 2 3
    oper2 = []
    combi = []
    for x, y in enumerate(oper):
        if y == 0:
            continue
        for i in range(y):
            if x == 0:
                x = "+"
            elif x == 1:
                x = "-"
            elif x == 2:
                x = "*"
            elif x == 3:
                x = '//'
            oper2.append(x)

    visited = [False for _ in range(N - 1)]
    result = []
    dfs(0)
    print(maxNum)
    print(minNum)

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

문제

문제

출처

ICPC

python 시간초과 질문입니다

ksungyoun 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말