글 읽기 - python3 시간초과가 되는 이유가 궁금합니다

vitriol95 2년 전 0

아마 17번째 라인이 문제가 되지 않나 생각을 계속 했는데, 수가 그렇게 크지 않을 뿐더러 리스트로 접근하기에 무리가 없을 것 같은데 이에 대한 이유가 궁금합니다. 아니면 다른 부분에서 오버가 되고있는 걸까요..?

import sys, math
sys.setrecursionlimit(int(1e6))
input = sys.stdin.readline

def solution(mod,bit):

    if bit == (1 << n) - 1:
        if mod == 0:
            return 1
        return 0

    if dp[mod][bit] != 0:
        return dp[mod][bit]

    for j in range(n):
        if not bit & (1 << j):
            new_mod = ((mod * mod_10[arr_length[j]]) % k + arr[j]) % k
            dp[mod][bit] += solution(new_mod, bit | 1 << j)

    return dp[mod][bit]

n = int(input())
arr = [input().rstrip() for _ in range(n)]
k = int(input())
arr_length = list(map(lambda x: len(x), arr))
arr = list(map(lambda x: int(x) % k, arr))

mod_10 = [1]
for i in range(50):
    mod_10.append((mod_10[-1]*10) % k)

dp = [[0]*(1 << n) for _ in range(k)]
answer = solution(0,0)

if answer == 0:
    print('0/1')
else:
    fact = math.factorial(n)
    if answer == fact:
        print('1/1')
    else:
        mod = math.gcd(answer, fact)
        print('{}/{}'.format(answer//mod, fact//mod))

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

문제

문제

출처

ICPC

python3 시간초과가 되는 이유가 궁금합니다

vitriol95 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말