글 읽기 - python 시간초과에 대한 질문

salvable 2년 전 0

분할정복 방식으로 풀고있는데 시간초과가 해결되지 않습니다. 

어디가 문제인지 모르겠습니다. 도와주세요

n, b = map(int, input().split(" "))

arr = []

def matrix_mult(A, B):
    n = len(A)
    temp = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                temp[i][k] += A[i][j] * B[j][k]
    return temp


def matrix_pow(A, n):
    if n == 1:
        return A

    if n % 2 == 0:
        temp = matrix_pow(A, n//2)
        return matrix_mult(temp, temp)

    else:
        temp = matrix_pow(A, n-1)
        return matrix_mult(temp, A)

for _ in range(n):
    arr.append(list(map(int, input().split(" "))))


arr2 = matrix_pow(arr,b)

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

ai4youej 2년 전 0

1. 빠른 입출력을 사용해보세요

2. matrix_mult에서 temp[i][k]를 %1000 하는 작업을 해주세요

alsrb0607 2년 전 0

재귀함수 중복 호출을 막기 위해 메모이제이션이 필요해보입니다.

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

문제

문제

출처

ICPC

python 시간초과에 대한 질문

salvable 2년 전 0

ai4youej 2년 전 0

alsrb0607 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말