10830

날짜 : 2023. 06. 21

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/10830

 

 

코드

import sys
sys.setrecursionlimit(10**9)

def mul(n1, n2):  # 두 행렬을 곱함
    a = n1 + n2
    # print("mul", n1, n2, a)
    if a in hash:  # 이미 해시에 있는 경우
        return  # 리턴
    # 없는 경우 -> 행렬간 곱셈
    mat1 = hash[n1]
    mat2 = hash[n2]
    temp = [[0] * N for _ in range(N)]
    for i in range(N): # 행
        for j in range(N):  # 열
            for k in range(N): temp[i][j] += (mat1[i][k] * mat2[k][j])
            temp[i][j] = temp[i][j] % 1000
    hash[a] = temp
    # print(a, hash[a])
    return

def func(num):
    if num in (0, 1): return
    else:
        n1 = (int(num // 2))
        n2 = num % 2
        # print(n1, n1, n2)
        # 해시에 없는 경우 체크
        if n1 not in hash:func(n1)
        if n1 * 2 not in hash: mul(n1, n1)
        if (n1 * 2 + 1) not in hash: mul(n1*2, 1)
        return


N, B = map(int, sys.stdin.readline().split())
graph = list()
for _ in range(N): graph.append(list(map(int, sys.stdin.readline().split())))
hash = dict()
hash[0] = [[1] * N for _ in range(N)]
hash[1] = graph

func(B)
for i in hash[B]:
    for j in i:
        print(j % 1000, end=" ")
    print()

 

 

풀이

- 제곱수이기 때문에 시간초과가 발생하지 않으려면 O(logN)으로 풀어야 한다.

- 그래서 각각의 계산결과를 hash에 저장한 후, 꺼내서 쓰는 방식으로 전개한다.

- 또한 값이 너무 커질 수 있기 때문에 1000으로 나눈 나머지값으로 저장한다.

 

 

알게된 점

- 분할 정복으로 풀이하는 것은 맞았지만 마지막에 결과값만 1000으로 나눈 나머지로 해야한다는 것으로 알았기 때문에 python3에서는 시간초과, pypy3에서는 메모리 초과가 발생했다.

- 그걸 고치니까 바로 통과됨... 

 

 

참고 사이트

-