글 읽기 - 파이썬 시간초과가 왜 나는지 모르겠습니다.

chchaeun 2년 전 0

divide 부분을 재귀로 돌렸을 땐 통과가 되는데 반복문으로 돌렸을 땐 안되는 것 같습니다. 이유가 뭘까요??

from copy import deepcopy
import sys; input=sys.stdin.readline
n, b = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
unit = [[1 if i==j else 0 for j in range(n)] for i in range(n)]

def calculate(X, Y):
    return [[sum(i*j for i, j in zip(xrow, ycol)) for ycol in zip(*Y)] for xrow in X]

def divide(a, b):
    result = deepcopy(unit)
    while(b):
        if b%2:
            result = calculate(result, a)
        a = calculate(a, a)
        b//=2
    return result

board = divide(board, b)

for i in board:
    for j in i:
        print(j%1000, end=" ")
    print()

seungwuk98 2년 전 1

8번 줄을 다음과 같이 수정하면 통과합니다.

    return [[sum(i*j%1000 for i, j in zip(xrow, ycol)) for ycol in zip(*Y)] for xrow in X]

chchaeun 2년 전 0

연산이 커져서 그런 거였군요 감사합니다!!

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

문제

문제

출처

ICPC

파이썬 시간초과가 왜 나는지 모르겠습니다.

chchaeun 2년 전 0

seungwuk98 2년 전 1

chchaeun 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말